[LeetCode] 198. House Robber

문제

https://leetcode.com/problems/house-robber/

House Robber - LeetCode

———————————————————————————

 

잠깐만

백준, 포도주 시식 문제 기억나세요?

https://skillist.tistory.com/233?category=258048 

DP - 2156. 포도주 시식

———————————————————————————

 

코드

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var maxResult = 0
        var maxSums: [Int] = Array(repeating: 0, count: nums.count)
    
        for index in 0..<nums.count {
            let indexFrom2 = index - 2 
            if indexFrom2 >= 0 {
                maxSums[index] = maxSums[indexFrom2]
            }
        
            let indexFrom3 = index - 3
            if indexFrom3 >= 0 {
                maxSums[index] = max(maxSums[index], maxSums[indexFrom3]) 
            }
            maxSums[index] += nums[index]
            maxResult = max(maxResult, maxSums[index])
        }
        return maxResult
    }
}

———————————————————————————

 

설명

백준의 포도주 문제 뿐만 아니라,

LeetCode에서 함께 풀었던, 문제와 로직이 같습니다.

322. Coin Change

377. Combination Sum IV

 

2만큼 이전 값을 가져오고

3만큼 이전 값을 가져와서 max값을 계산해 나가면 됩니다.

———————————————————————————

 

회고

오랜만에 알고리즘을 시작했더니,

몸풀기 문제들을 던져주는 느낌이에요.

그런데 난이도는 미디움이네요..?