[JAVA] 동적프로그래밍(DP) "도둑질"

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

 

개미병사들이 집을 한칸 건너 터는 문제와 비슷하다.

유의할 점은,  집들이 아래와 같이 동그랗게 원으로 배치된다는 점이다.

첫번째 집과 마지막 집이 연결되므로 이 점을 케이스를 나누어서 생각해야한다.

 

• 기본적인 점화식은 아래와 같다.

A[n] = Max( A[n-2] + A[n] , A[n-1])

 

• 이 때, 첫번째 집이 선택되는경우와 아닌 경우로 나누어서

1. 첫번째 집이 선택되는 경우 : pick[0]

 

2. 첫번째 집이 선택되지 않는 경우 : pick[1]

 

두가지 케이스를  같이 for문에서 연산을 돌린다.

 

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

        pick[0][0] = money[0];
        pick[0][1] = money[0];
        pick[1][0] = 0;
        pick[1][1] = money[1];

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

        return Math.max(pick[0][pick[0].length-2], pick[1][pick[1].length-1]);
    }
}

 

그리고 두 케이스를 return문에서 최대값 비교를 하여 반환한다.

 

 

같은 방식이지만 좀 더 직관적인 코드

class Solution {
      public int solution (int[] money) {
    int[] dp1 = new int[1000000]; // 첫 번째 집을 터는 경우
    int[] dp2 = new int[1000000]; // 두 번째 집을 터는 경우

    int N = money.length-1;

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

    // 마지막 집 전까지 반복문 순회 (마지막 집은 첫 번째 집을 터냐 안터냐에 상관있기 때문이다.
    for (int i=2; i<N; i++) {
      dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i]);
      dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i]);
    }

    dp1[N] = dp1[N-1];
    dp2[N] = Math.max(dp2[N-1], dp2[N-2] + money[N]);

    return Math.max(dp1[N], dp2[N]);
  }
}