[leetcode] 198. House Robber [kotlin]

문제분석

1. dp 문제이다.

2. nums input 으로 각 집에있는 돈 양이 들어온다.

3. nums array에 연속된 인덱스는 인접한 집으로 판단한다.

4. 인접한 집을 털 수 없다.

 

문제해결

1. 도둑이 선택할 수 있는 방법은 두가지이다. 현재 집을 털거나 털지 않거나이다.

2. 현재 집을 턴다면 바로 전 집을 털 수 없기 때문에, 전 집을 털었을 때의 최대 돈과 전전집을 털고 현재 집을 털었을 때, 최대 돈을 비교하여 현재 집 기준으로 최대 돈을 구한다.

3. 현재가 i라고 한다면 [i의 최대돈] = max([i-1 까지의 돈], [i-2 까지의 돈] + [i를 털었을때 돈] 이다.

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 1) return nums[0]
        val dp = IntArray(nums.size) { 0 }
        dp[0] = nums[0]
        dp[1] = maxOf(nums[1],nums[0])
        for (i in 2..nums.size-1) {
            dp[i] = maxOf(dp[i-1], dp[i-2] + nums[i])
        }

        return dp[nums.size-1]
    }
}