[프로그래머스 알고리즘 고득점 Kit][동적계획법(Dynamic Programming)][Java] 도둑질

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

프로그래머스

이 문제에서 가장 중요한 것은 원형이기 때문에
첫 번째 집을 선택했냐 안 했냐입니다.
첫 번째 집을 선택하면 마지막 집을 선택하지 못합니다. 
그렇기 첫번째 집을 선택했다는 "상태"를 마지막까지 기억해야 합니다.

그래서 dp 배열을 2개로 분리하여 
선택한 dp, 선택하지 않은 dp를 분리하여 진행합니다.

그러면 각 dp도 이전에 선택했는지 안 했는지 알아야 하기 때문에 [i][0], [i][1] 이런 식으로 i번째 선택, i번째 선택 x로 
다음 집을 선택할 수 있냐 없냐를 분리하여 최대를 업데이트해갑니다.

최종 2개의 배열을 모두 순회했을 때 더 큰 값이 최대가 됩니다.

하지만 이렇게 하면 
시간초과로 틀리게 됩니다.

 

1. 틀린 코드

class Solution {
    public int solution(int[] money) {
        int len = money.length;

        int[][] dp1 = new int[2][len];

        dp1[0][0] = 0;
        dp1[1][0] = money[0];

        for(int i=1; i<len-1; i++) {
            dp1[0][i] = Math.max(dp1[0][i-1], dp1[1][i-1]);
            dp1[1][i] = dp1[0][i-1] + money[i];
        }

        int result1 = Math.max(dp1[0][len-2], dp1[1][len-2]);

        int[][] dp2 = new int[2][len];

        dp2[0][1] = 0;
        dp2[1][1] = money[1];

        for(int i=2; i<len; i++) {
            dp2[0][i] = Math.max(dp2[0][i-1], dp2[1][i-1]);
            dp2[1][i] = dp2[0][i-1] + money[i];
        }

        int result2 = Math.max(dp2[0][len-1], dp2[1][len-1]);

        return Math.max(result1, result2);
    }
}

O(N)라 데이터의 값이 100만 개라도 괜찮을 거라 생각했습니다.

하지만 틀린 결과를 보고 
가장 의심해 볼 만한 것은 100만 개라는 적지 않은 데이터라 생각하고

배열을 쓰지 않아 보기로 했습니다.
왜 그래도 된다고 생각했냐면 이 코드의 점화식은 단순히 이전에 선택했을 때 안 했을 때만을 이용하기 때문에
합을 하나의 변수로 업데이트하는 식으로 해도 문제없을 거라 판단했습니다.

 

2. 정답 코드

class Solution {
    public int solution(int[] money) {
        int len = money.length;

        int pick = money[0]; //첫번째 집 선택 -> 마지막 집 선택 못함
        int notPick = 0; 
        for(int i=1; i<len-1; i++) { //len-2까지 마지막 집 선택 못함
            int nextNotPick = Math.max(notPick, pick); //다음 집을 선택안한다. -> 지금 집을 선택 안했을 때, 지금 집을 선택했을 때 값 중 큰 걸 기억함
            int nextPick = notPick + money[i]; //다음 집을 선택한다. -> 지금 집 선택 안했을 때 값 + 다음 집 선택

            notPick = nextNotPick;
            pick = nextPick;
        }

        int resultFirstPick = Math.max(notPick, pick);

        pick = money[1]; //두번째 집 선택 -> 마지막 집 선택 가능
        notPick = 0;
        
        for(int i=2; i<len; i++) { //len-1 까지 마지막 집 선택 가능
            int nextNotPick = Math.max(notPick, pick); //다음 집을 선택안한다. -> 지금 집을 선택 안했을 때, 지금 집을 선택했을 때 값 중 큰 걸 기억함
            int nextPick = notPick + money[i]; //다음 집을 선택한다. -> 지금 집 선택 안했을 때 값 + 다음 집 선택

            notPick = nextNotPick;
            pick = nextPick;
        }

        int resultFirstNotPick = Math.max(notPick, pick);
        
        return Math.max(resultFirstPick, resultFirstNotPick);
    }
}

결과는 통과.

이 바꾼 코드의 시간복잡도도 O(N)이지만 왜 맞았을까?

원인 분석이라 한다면 
100만 개의 배열을 생성하는 것은 공간 할당과 동시에 0으로 채워지는 비용이 
적은 시간이 아니다라고 결론을 내렸습니다.