[PG] 도둑질 [C++]

 

프로그래머스

 

1시간 고민하고도 모르겠어서 질문 게시판에 있는 힌트를 봤지만, 문제를 애초에 잘못이해해서 힌트도 이해를 못 한 거였다;;

 

 

이 지문을 잘못이해해서, 내 양쪽 집이 둘 다 털리면 경보가 울리는 것으로 생각했었다.

그래서 첫 번째 집과 마지막 집에 포커스를 둘게 아니라, 첫 번째 집을 터느냐 마느냐만 생각하면 된다는 힌트도 이해를 못 했었다.

 

지문을 제대로 풀어보면 그냥 연속으로 집을 털지 말란 거다.

(이 쉬운걸 왜 못 알아먹었을까)

 

2차원 배열로 DP 배열을 만들었고, DP[i][0]은 0번째 집을 털지 않았을 때, DP[i][1]은 0번째 집을 털었을 때로 생각하고 코드를 작성했다.

 

DP[i][0] = max(DP[i - 2][0] + money[i], DP[i - 1][0]) 이다.

i - 2번째 집도 털고, i번째 집도 터는 경우 vs  i - 1번째 집을 털고 i번째 집은 털지 않는 경우다.

DP[i][1]도 똑같지만, 마지막 집에서 식이 다르다. 0번째 집을 이미 털었기 때문에 N - 1번째 집은 털면 안 되기 때문이다.

 

코드

#include <string>
#include <vector>

using namespace std;

int N;
int dp[1000001][2]; // 0 - don't steal 0th home, 1 - steal 0th home

int solution(vector<int> money) {
    int answer = 0;
    N = money.size();
    
    dp[0][0] = 0;
    dp[0][1] = money[0];
    dp[1][0] = money[1];
    dp[1][1] = max(money[0], money[1]);
    for (int i = 2; i < N; i++) {
        dp[i][0] = max(dp[i - 2][0] + money[i], dp[i - 1][0]);
        if (i == N - 1) {
            dp[i][1] = max(dp[i - 2][1], dp[i - 1][1]);
        } else {
            dp[i][1] = max(dp[i - 2][1] + money[i], dp[i - 1][1]);
        }
    }

    answer = max(dp[N - 1][0], dp[N - 1][1]);
    return answer;
}