# [프로그래머스] Lv 4. 도둑질 - 동적계획법

문제 : 도둑질 (opens new window)

# 문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

# 제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

# 입출력 예

# 문제 풀이

• 인접한 두 집을 털지 못한다.
• n번째 집까지 계산했을 때 훔칠수 있는 돈의 최대 값은
  (n-2집까지 계산했을 때 최대값 + n번째 집의 돈) vs n-1집까지 계산했을 때 최대값 중에 큰 값이다.
• 즉, 아래와 같이 표현할 수 있다.

  dp[i] = max(dp[i-2] + money[i], dp[1])

• 첫번째 집을 털 경우에는 마지막집을 털지 못한다.
• 첫번째 집을 터는 경우와 털지 않는 경우, 2가지를 계산하여 둘 중에 큰 값을 return한다.

# 코드 구현

• 첫번째 집을 터는 경우에 대한 메모이제이션 배열 dp1을 생성한다.

• 첫번째 집을 털지 않는 경우에 대한 메모이제이션 배열 dp2을 생성한다.

• dp1의 경우, 첫번째 집을 털기 때문에 두번째 집은 털지 못한다.

  dp1[0] = money[0], dp1[1] = money[0]

  • 마지막 집은 계산하지 말아야 하므로 moeny.length - 1 번째까지 반복하여 최대 값을 구한다.

• dp2의 경우, 첫번째 집은 털지 않으므로 첫번째 집의 값을 0으로 두고 계산한다.

  dp2[0] = 0, dp2[1] = money[1]

• money.length 번째까지 반복하여 최대 값을 구한다.

• dp1[money.length - 2], dp2[money.length -1] 중 더 큰 값을 return 한다.

# Java

class Solution {
  public int solution(int[] money) {
      int len = money.length;
      int[] dp1 = new int[len-1];
      int[] dp2 = new int[len];
      
      dp1[0] = money[0];
      dp1[1] = money[0];
      dp2[0] = 0;
      dp2[1] = money[1];
      
      for(int i=2; i<len-1; i++) {
          dp1[i] = Math.max(dp1[i-2] + money[i], dp1[i-1]);
      }
      for(int i=2; i<len; i++) {
          dp2[i] = Math.max(dp2[i-2] + money[i], dp2[i-1]);
      }
      return Math.max(dp1[len-2], dp2[len-1]);
  }
}