[LeetCode] House Robber

문제

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

예시

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

---

풀기

문제를 요약하자면 강도는 이틀에 한 번 집을 털 수 있고 최대로 이익을 낼 수 있는 값을 출력하라는 말이다.

즉, 배열의 값이 반복되지 않도록 하라는 뜻.

 

DP 문제에 해당하므로 점화식을 찾도록 하자.

집을 반복해서 털 수 없다고 했으니

• dp[i - 2] + nums[i] -> 현재 집 털기
• dp[i - 1] -> 현재 집 털지 않기
• 현재 집을 털지 않기 or 현재 집과 이전 집을 건너뛰고 털기 중 최댓값 선택

따라서 점화식은 아래와 같다.

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

 

---

결과

class Solution {
    fun rob(nums: IntArray): Int {
        var prev1 = nums[0] // 이전 집 (dp[i - 1])
        var prev2 = 0 // 전전 집 (dp[i - 2])

        for (i in 1 until nums.size) {
            val current = maxOf(prev1, nums[i] + prev2)
            prev2 = prev1
            prev1 = current
        }

        return prev1
    }
}