Today's Algorithm(2019-01-17)

programmers. 도둑질

동적계획법 문제는 정말 동적계획법답게 풀지 않으면 시간 초과나 메모리 초과가 발생하는데 이 때문에 많은 고생을 했습니다. 처음엔 머리에 떠오르는대로 재귀로 풀었는데요. 모든 경우의 수를 다 돌다보니 역시나 시간초과부터 발생하더라구요. 그리고 이후엔 학교에서 배운대로 배낭문제나 최소 잔돈개수 문제처럼 표를 떠올리며 구현하였습니다. 여기서 정확성 테스트에서 시간 초과는 극복할 수 있었지만 효율성 테스트에서 시간 초과 및 메모리 초과가 발생하여 이 또한 통과하지 못하였습니다. 우선 메모리초과가 발생한 이유는 array[length][length] 로 만들었기 때문인데요. 다른 사람의 코드를 참고하면서 굳이 저렇게 배열을 모두 만들지 않더라도 해결할 수 있음을 알게되었습니다.

 

두 가지의 경우를 고려합니다. 이렇게 두 가지를 고려하는 이유는 맨 처음과 맨 뒤가 이어져있기 때문입니다. 동적계획법에 따라 Math.max(dp[i - 1], dp[i - 2] + money[i]) 로 배열을 채우게 될 것입니다. 글로 풀어 말하면 (바로 앞집 인덱스의 최대값, 바로 앞앞집 최대값과 자신의 값) 중에서 선택하는 것입니다. 최대값에 대해선 생각하지 않아도 됩니다. 앞에서부터 저절로 최대가 되는값으로 채워지게 될테니까요. 이렇게 하게되면 인덱스는 2부터 시작하는 것이 가장 편합니다.

• 처음이 포함되는 경우

  • 처음이 선택되면 자동적으로 두번째 집은 첫번째 집의 최대값과 같습니다. 그 이유는 인접해있기 때문이죠. 별도로 배열에 값을 넣어줘야 합니다.
  • 그리고 첫번째가 선택되는 바람에 맨 마지막도 선택되지 않아야하므로 이후 최대값을 선택할 때 length - 2 번째가 최대값이 됩니다.

• 처음이 포함되지 않는 경우

  • 처음이 포함되지 않으면 그 값은 0이 되어야합니다. 배열은 선언하면 초기값이 0으로 선언되어 있기 때문에 이는 별도로 설정하지 않아도 됩니다.
  • 반복문 인덱스가 2부터 시작하기 때문에 첫번째 집은 값을 채워넣어줘야 합니다.

• 세 집만 주어지는 경우

  • 위 동적계획법이 통과하지 못하는 경우가 있는데요. 이 경우는 세 집만 주어질 때입니다. 동적계획법에서 하는 설정때문에 최대값을 찾기 어려운 것이죠.
  • 세 집만 주어지면 그 중 가장 큰 값만 고르면 되기 때문에 Math.max 을 2번 사용하면 됩니다.

그럼 이제 코드를 살펴볼까요?

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

        if(length == 3) {
            return Math.max(money[0], Math.max(money[1], money[2]));
        }

        int[] dp = new int[length];  // 처음 포함
        dp[0] = money[0];
        dp[1] = money[0];
        int[] dp2 = new int[length];  // 처음 포함x
        dp2[0] = 0;
        dp2[1] = money[1];

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

        return Math.max(dp[length - 2], dp2[length - 1]);
    }
}