[프로그래머스, 42897] 도둑질 (java)

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

프로그래머스

---

메모리: 109 MB, 시간: 45.15 ms

사용 알고리즘: 동적계획법（Dynamic Programming)

 

이 문제를 해결한 기본적인 아이디어는,

dp 배열에 i번째 집을 털었을 때의 최댓값, i번째 집을 털지 않았을 때의 최대값을 저장한다.

i번째 집을 털기 위해선 이웃한 집을 털 수 없으므로 무조건 i - 1번째 집을 털지 않았을 경우의 최대값을 가져와야 하고

i번째 집을 털지 않으면, i - 1번째 집을 털던 털지 않던 상관없으므로 둘 중 더 큰 경우 값을 가져온다.

// i번째 집을 터는 경우
dp[i][0] = dp[i - 1][1] + money[i];

// i번째 집을 털지 않는 경우
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);

 

하지만 이 마을은 집들이 동그랗게 배치되어 있다.

0번째 집과, 마지막 집이 연결되어 있다.

즉, 마지막 집은 바로 전 집 뿐만 아니라 0번째 집까지 신경 써주어야 한다.

하지만 위의 방법으로는 마지막 집을 연산할 때, 0번째 집이 포함되어 있는지 포함되지 않았는지 알기 어렵다.

따라서 0번째 집이 포함되어 있는 경우와 포함되지 않은 경우도 따로 계산해 주었다.

// i번째 집을 터는 경우(0번째 집도 털었음)
dp[i][0] = dp[i - 1][2] + money[i];

// i번째 집을 터는 경우(0번째 집은 털지 않았음)
dp[i][1] = dp[i - 1][3] + money[i];

// i번째 집을 털지 않는 경우(0번째 집은 털었음)
dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][2]);

// i번째 집을 털지 않은 경우(0번째 집도 털지 않았음)
dp[i][3] = Math.max(dp[i - 1][1], dp[i - 1][3]);

 

마지막으로, 위의 예시에선 dp 배열을 2차원 배열로 만들었다.

하지만 2차원 배열로 만들 경우 효율성 검사에서 3문제가 시간초과가 떴다.

처음엔 1,000,000개에 대하여 dp를 각 4번씩 밖에 연산하지 않는데 왜 시간초과가 떴는지 몰라 다른 방법을 생각해 보다 질문하기를 참고했는데, 2차원 배열을 1차원 배열로 바꾸면 풀린다는 말을 보고 1차원 dp 배열을 4개로 나누어 제출해 보았더니 풀렸다.

gpt한테 2차원 배열을 선언해서 사용하는 것과 1차원 배열을 선언해서 사용하는 것의 시간, 속도 차이점에 대해 물어보니 2차원 배열의 요소에 접근할 때, 두 번의 인덱스 연산이 필요해 1차원 배열에 비해 약간의 성능 저하가 있을 수 있다고 한다. 근데 그게 시간 초과가 날 정도로 크리티컬 한 성능 저하인지는 모르겠다...

 

class Solution {
    public int solution(int[] money) {
        
        // dp1[i] := i번째 집을 털었을 경우의 최대값(턴 집 리스트에 0번째 집이 포함되어 있음)
        // dp2[i] := i번째 집을 털었을 경우의 최대값(턴 집 리스트에 0번째 집이 포함되어 있지 않음)
        // dp3[i] := i번째 집을 털지 않았을 경우의 최대값(턴 집 리스트에 0번째 집이 포함되어 있음)
        // dp4[i] := i번째 집을 털지 않았을 경우의 최대값(턴 집 리스트에 0번째 집이 포함되어 있지 않음)
        int[] dp1 = new int[money.length];
        int[] dp2 = new int[money.length];
        int[] dp3 = new int[money.length];
        int[] dp4 = new int[money.length];
        
        dp1[0] = money[0];
        for(int i = 1; i < money.length - 1; i++) {
            // i번째 집을 터는 경우, i - 1번째 집은 무조건 털 수 없음
            dp1[i] = dp3[i - 1] + money[i];
            dp2[i] = dp4[i - 1] + money[i];
            
            // i번째 집을 털지 않는 경우. i - 1번째 집은 털거나 털지 않거나 상관 없음
            // 더 큰 경우를 저장
            dp3[i] = Math.max(dp1[i - 1], dp3[i - 1]);
            dp4[i] = Math.max(dp2[i - 1], dp4[i - 1]);
        }
        
        // 0번째 집과 마지막 집도 인접해 있으므로
        // 마지막 집을 터는 경우, 턴 집 리스트에 0번째 집이 포함되어 있으면 안됨.
        int last = money.length - 1; // 마지막 집 인덱스
        
        // 0번째 집 털지 않고 마지막 집 터는 경우
        dp2[last] = dp4[last - 1] + money[last];
        
        // 0번째 집을 털은 경우 중, 마지막 전 집을 터는 경우와 털지 않은 경우 중 큰 수와 비교
        dp3[last] = Math.max(dp1[last - 1], dp3[last - 1]);
        
        // 0번째 집을 털지 않은 경우 중, 마지막 전 집을 터는 경우와 털지 않은 경우 중 큰 수와 비교
        dp4[last] = Math.max(dp2[last - 1], dp4[last - 1]);
        
        int answer = Math.max(dp2[last], dp3[last]);
        answer = Math.max(answer, dp4[last]);
        
        return answer;
    }
}