[Programmers] 도둑질

난이도 : Level 4

문제링크

• 마을의 모든 집들은 동그랗게 배치되어 있다.
• 각 집들은 서로 인접한 집들과 방법장치가 연결되어 있음
  • 인접한 두 집을 털면 경보가 울림
• 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구하시오

 

해설

• 집들이 원형으로 배치되어 있고 인접한 두 집을 털 수 없으므로 두가지 경우가 발생한다
  • 첫번째 집을 털면 마지막 집을 털지 못하고
  • 마지막 집을 털면 첫번째 집을 털지 못한다
• 두가지 경우를 비교하고, 가장 큰 값을 리턴한다
  • 첫번째 집부터 마지막에서 이전 집까지 터는 돈의 최대값
  • 두번째 집부터 마지막까지 터는 돈의 최대값

 

public int solution(int[] money) {
    int size = money.length;
    int[] dp1 = new int[size];
    int[] dp2 = new int[size];

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

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

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

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

    return Math.max(dp1[size-2], dp2[size-1]);
}

• i번째까지 털었을 때의 최대값을 저장하는 배열을 선언한다
• dp1 : 첫번째 집부터 마지막에서 이전 집까지 털 때의 최대값을 담은 배열
• dp2 : 두번째 집부터 마지막까지 털 때의 최대값을 담은 배열

 

 

참고

• 전현서 - 프로그래머스 해설