Swift) LeetCode(Easy) - House Robber (DP)

leetcode.com/problems/house-robber/

House Robber - LeetCode

안녕하세요 후르륵짭짭 입니다.

문제 해설 바로 가겠습니다.

 

** 문제 **

도둑이 집을 털려는데, 연속된 집은 경찰 경보기 때문에 훔칠 수 없다고 합니다. 그래서 연속된 집은 털지 않고

최대로 훔질 수 있는 양을 출력하라고 합니다.

 

** 저의 해결 방법 **

 일단 저는 DP가 약하기 때문에, 이 문제에 대해서 바로 생각하지 못 했습니다.

[2,7,9,3,1] 이 있을 때,,,

이렇게 밑에서 부터 위로 올라가는 식으로 처음에 생각 했는데,,,,

이렇게 하면 경우의 수가 많아지고,,, 복잡해진다는 생각을 해서 아닐 것 같아

다시 생각 했습니다.

곰곰히 생각 하니, 이렇게 위에서 아래로 찾아가는 방법을 생각하게 되었고 이러한 방법으로 코딩을 짰습니다.

class Solution {
    
    func rob(_ nums: [Int]) -> Int {
            
        var sumList : [Int] = Array(repeating: 0, count: nums.count)
        
        for (index,element) in nums.enumerated(){
            
            if index == 0 || index == 1 {
                sumList[index] = element
            }
            else if index == 2 {
                sumList[index] = element + sumList[0]
            }
            else{
                let beforeOne = element + sumList[index - 2]
                let beforeTwo = element + sumList[index - 3]
                
                let maxSum = max(beforeOne, beforeTwo)
                
                sumList[index] = maxSum
            }
            
        }
        
        
        return sumList.max() ?? 0
        
    }
    
}

이렇게 반복문을 돌려 sumList에 합을 저장해주고 그 합 중에서 가장 큰 값을 출력해주도록 코드를 완성 했습니다.

 

** 다른 사람의 코드 **

bongbenglengkeng 님의 코드 입니다.

class Solution {
    func rob(_ nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        
        var r: [Int] = []
        for (index, num) in nums.enumerated() {
            if index == 0 {
                r.append(num)
            } else if index == 1 {
                r.append(max(r[0], num))
            } else {
                r.append(max(r[index-1], r[index-2] + num))
            }
        }
        return r.last!
    }
}