[프로그래머스] 42897 도둑질

https://programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

 

이 문제는 백준의 RGB거리 2와 매우 비슷합니다. RGB거리2를 풀고 오면 아주 수월하게 풀 수 있을 것입니다.

이 문제는 1번째와 N번째가 연결되는 원형모양을 띄는 경우, 즉 1번째와 N번째가 연결되어 있다는 것을 의미하고 있습니다. 그렇기 때문에 1번째가 선택되지 않았을 경우에 N번째를 선택하는 경우, 1번째를 선택했을 때 N번째를 선택하지 않은 경우 두 경우에서 나올 수 있는 최대값을 구하면 됩니다.

DP 문제를 풀기 위해서는 점화식의 규칙을 알아야 합니다. 좀 더 쉽게 설명하기 위해 아래의 예는 선형으로 되어있다고 가정해 보겠습니다.

 [2, 2, 3, 4, 3, 2, 5] 라는 경우가 있다고 해봅시다.

1번째 : [2, 2, 3, 4, 3, 2, 5]
1번째의 경우는 이전에 고려해야할 경우가 없기 때문에 1번째 값만을 가집니다.
DP : [2, 0, 0, 0, 0, 0, 0]

2번째 : [2, 2, 3, 4, 3, 2, 5]
2번째의 경우는 이전에 고려해야할 경우가 1번째이고, 1번째를 털고 2번째를 터는 경우는 없기 때문에 2번째 값만을 가집니다.
DP : [2, 2, 0, 0, 0, 0, 0]

3번째 : [2, 2, 3, 4, 3, 2, 5]
3번째의 경우에 붙어있는 2번째 집은 털지 못합니다. 1번째 집을 털고 난 후에 3번째 집을 터는 경우가 가장 큰 돈을 벌기 때문에 1번째 + 3번째 값을 얻게 됩니다.
DP : [2, 2, 5, 0, 0, 0, 0]

4번째 : [2, 2, 3, 4, 3, 2, 5]
4번째의 경우가 조금 복잡할 수 있습니다. 일단 붙어있는 3번째 집은 못 터니까 패스!
2번째의 집을 털고, 4번째 집을 터는 경우가 있습니다. 여기서 2번째의 집은 이전의 값들을 모두 고려한 2번째 집의 값이 될 것입니다.
또 다른 경우는, 2번째 집을 털지 않고 1번째 집을 털고 4번째 집을 털 수도 있습니다.. 만약 [100, 2, 3, 4, ...] 인 경우에 100 + 4가 2 + 4보다 크기 때문입니다. 물론 이 경우에는 두 경우의 값이 같으니까 값은 6!
이게 끝인 것 같지만, 누적된 2번째 + 4번째/1번째 + 4번째의 경우 모두 고려했지만, 누적된 3번째 값이 훨씬 큰 경우도 있습니다. (어휴 많다!)
따라서 이 세가지 경우를 모두 고려해야 합니다.
DP : [2, 2, 5, 6, 0, 0, 0]

이러한 과정을 거치면 답을 구할 수 있습니다. 물론 위의 경우는 선형일 때를 가정한 것이기 때문에 원형인 현재 문제를 고려하기 위해서는 1번째 집을 턴 경우 & N번째 집을 털지 않은 경우, 그리고 1번째 집을 털지 않은 경우 & N번째 집을 턴 경우를 나누어 계산해야 합니다.

아래는 코드입니다.

class Solution {
    public int solution(int[] money) {
        int answer = 0;

        // init
        int N = money.length;

        int[] dp = new int[N];
        int[] dp2 = new int[N];

        // 0번째 집을 털었을 때
        dp[0] = money[0];
        if (N > 1) dp[1] = money[1];
        for (int i = 2; i < N - 1; i++) {
            if (i == 2) dp[i] = dp[i - 2] + money[i];
            else dp[i] = Math.max(dp[i - 2] + money[i], Math.max(dp[i - 1], dp[i - 3] + money[i]));
            
            answer = Math.max(answer, dp[i]); 
        }

        // 0번째 집을 안 털었을 때
        dp2[0] = -1000 * 1000000; // 가장 작은 값으로 초기화
        if (N > 1) dp2[1] = money[1];
        for (int i = 2; i < N; i++) {
            if (i == 2) dp2[i] = money[i];
            else dp2[i] = Math.max(dp2[i - 2] + money[i], Math.max(dp2[i - 1], dp2[i - 3] + money[i]));

            answer = Math.max(answer, dp2[i]);
        }
        
        return answer;
    }
}