순위

1. 문제 설명

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

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

[제한사항]

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.

• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

Example 1) money = [1, 2, 3, 1]

result = 4

2. 이론

< 동적 프로그래밍 (Dynamic Programming) >

복잡한 문제를 간단한 여러 문제로 나누어 푸는 것

DP의 핵심은 이전에 풀었던 문제에 대하여 저장 공간에 저장해 둔 뒤 계산 과정에서 다시 가져올 수 있어야 한다.

3. 해결 Point

이 문제의 핵심은 도둑이 인접한 두 집을 털수 없다는 점이다. 이 점을 이용해서 배열에 있는 index 0 과 1 둘 중에 한 곳에서 출발해서 다음 집을 털었을 때 최대 값을 계산하는 방식으로 진행한다.

0 -> 2 -> 4 -> 6 -> 7 -> 5 -> 7 -> 8 -> 3 -> 5 -> 7 -> 8 -> 6 -> 8 -> 9 1 -> 3-> 5 -> 7 -> 8 -> 6 -> 8 -> 9 -> 4 -> 6 -> 8 -> 9 -> 7 -> 9 -> 10

두개의 배열을 만들어서 하나는 index 0으로 시작하는 배열 하나는 index 1로 시작하는 배열로 만들어서 다음 집을 털었을 떄 최대값을 순차적으로 구한다.

class Solution {
  public int solution(int[] money) {

    // index 0 배열, n-1 번째 집가지 턴다.
    int[] dp0 = new int[money.length-1];
    // index 1 배열, n 번째 집가지 턴다.
    int[] dp1 = new int[money.length];

    // 초기화
    dp0[0] = money[0];
    dp0[1] = money[0];
    dp1[0] = 0;
    dp1[1] = money[1];

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

    return Math.max(dp0[money.length-2], dp1[money.length-1]);
  }
}

4. Source Code

class Solution {
  public int solution(int[] money) {
    int answer = 0;

    int[] dp0 = new int[money.length-1];
    int[] dp1 = new int[money.length];

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

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

    return Math.max(dp0[money.length-2], dp1[money.length-1]);
  }
}