[LeetCode] 198. House Robber

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

House Robber - LeetCode

House Robber - Medium

 

당신은 전문 도둑이다. nums는 집집마다 가진 현금 액수를 의미한다. 집에서 현금을 훔칠 수 있는데, 두 집을 연속으로 훔치면 경찰에 연락이 가 발각되고 만다. 이 때 최대로 훔칠 수 있는 현금은 얼마인지 구하는 문제다.

 

이 전에 주식관련 문제와 비슷하며 훨씬 쉬운 문제다.

각 집에 들렀을 때 도둑의 상태(state)는 두 가지 뿐이다.

 

1. 이 전에 현금을 훔치지 않아 현금을 훔칠 수 있는 상태 => state[0]

2. 이 전에 현금을 훔쳐 더이상 훔칠 수 없는 상태 => state[1]

 

각각의 상태일때 훔진 최대 현금을 dp식으로 저장해주면 된다.

 

1번 상태가 되기 위해서는

1) 이전집에서 1번상태(훔칠 수 있는 상태)이고, 이번 집에서도 현금을 훔치지 않았을 때

2) 이전집에서 2번상태(훔칠 수 없는 상태)이고, 이번 집에서는 현금을 훔치지 않았을 때

 

두가지 케이스가 있다.

따라서 state[0] = max(state[0], state[1])

 

2번 상태가 되기 위해서는

1) 이전집에서 1번상태 (훔칠 수 있는 상태)이고, 이번 집에서 현금을 훔쳤을 때

2) 이전집에서 2번상태 (훔칠 수 없는 상태)였다면 더 훔칠 수 없으므로 될 수 없다.

 

그러므로 한가지 케이스 뿐이다.

따라서 state[1] = state[0] + num

으로 dp식을 완성시켜 주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int rob(vector<int>& nums) {
        int s[2] = {},t;
        for (int n:nums) {
            t = s[0];
            s[0] = max(s[0], s[1]);
            s[1] = t + n;
        }
        return max(s[0],s[1]);
    }
};