[PS] 프로그래머스 Lv4 : 도둑질(Java)

문제

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

프로그래머스

 

---

풀이

다이나믹 프로그래밍 풀이

접근법

나는 보통 DP 문제를 풀 때 각 원소에서 선택할 수 있는 최선의 값을 고르는 점화식을 생각한다.

이 문제도 동일한 방식으로 접근했고, i번째 집을 털 경우와 털지 않는 경우 두 가지 중 최대값을 선택하는 점화식을 생각했다.

 

처음 생각한 점화식은 다음과 같다.

DP[i] = Math.max(DP[i-1], DP[i-2] + money[i])

 

1. DP[i-1]의 경우 현재 집을 털지 않았을 때
2. DP[i-2] + money[i]의 경우 전전 집을 털었을 때

 

하지만 결과는 40점.. 원형 큐라는 특성을 고려하지 않은게 문제였다.

 

[20, 10, 5, 6, 30] 이라는 배열이 있을 때, 위 점화식을 토대로 진행해보면 다음과 같다.

i == 1 DP = [20, 0, 0, 0, 0] 자기자신을 선택하는게 최선

i == 2 DP = [20, 20, 0, 0, 0] 현재 집을 털지 않는게 최선

i == 3 DP = [20, 20, 25, 0, 0] 현재 집을 터는게 최선

i == 4 DP = [20, 20, 25, 26, 0] 현재 집을 터는게 최선

i == 5 dp = [20, 20, 25, 26, 55] 현재 집을 터는게 최선

 

여기서 문제가 발생한다. 55이라는 해가 나오기 위해서는 첫 번째 원소(20)와 2번째 원소(5)와 마지막 원소(30)를 털어야 한다. 위 점화식 대로라면 이렇게 선택이 될 것이다.

 

하지만 원형 큐라는 특성을 생각하면 첫 번째 원소(20)와 마지막 원소(30)는 동시에 털지 못한다.

정답부터 말하자면 40이다.

 

그렇다면 어떻게 이러한 특성을 고려하여 선택을 해야할까?

답을 찾아본 결과 나이스하게 간단했다.

 

탐색을 할 때 money원소의 길이를 조정하는 것이다.

총 두번의 탐색을 돌리게 될텐데,

첫 번째는 첫 번째부터 마지막 전까지 (money[0] ~ money[money.length-2])

두 번째는 두 번쨰부터 마지막까지 탐색을 수행하는 것이다. (money[1] ~ money[money.length-1])

이렇게 될 경우 첫 번째 탐색에서는 첫 번째 원소와 마지막 원소가 선택될 경우가 없지만 마지막 원소를 고려한 케이스가 없어진다.

 

이를 해결하기 위해 두 번째 탐색을 통해 첫 번째 원소를 고려하지 않고 마지막 원소를 고려하는 것으로 두 탐색의 결과값을 비교한다.

탐색의 결과를 한번 확인해보자.

money : [0, 20, 10, 5, 6] → DP : [0, 20, 20, 25, 26]

money : [0, 10, 5, 6, 30] → DP : [0, 10, 10, 16, 40]

두 결과의 최대값을 뽑아내면 40이 됨으로 정해가 나오는 것을 확인할 수 있다.

이 로직을 토대로 소스코드를 구현해보자.

---

소스코드

import java.util.Arrays;
class Solution {
    public int solution(int[] money) {
        int res = 0;
        
        int[] dp = new int[money.length];
        
        dp[1] = money[0];
        for(int i=2; i<money.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + money[i-1]);
        }
        
        res = dp[dp.length-1];
        Arrays.fill(dp, 0);
        
        dp[1] = money[1];
        for(int i=2; i<money.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + money[i]);
        }
        
        
        return Math.max(res, dp[dp.length-1]);
    }
}

 

---

정리

평소 복잡하지않은 다이나믹 프로그래밍에 대해서는 꽤나 자신이 있었지만, 자신 있던 이유가 정형화된 DP문제를 쉽게쉽게 풀었었기 때문이라고 생각한다.

 

이번 문제에서는 원형 큐라는 특성을 고려해야했던 점이 조금 어려운 부분이라고 생각하고 또 하나 알아갈 수 있었다.