[프로그래머스/level 4] 도둑질 (문제/정답/풀이)

문제

프로그래머스

 

정답

def solution(money):  
    dp1 = [0] * len(money)
    dp2 = [0] * len(money)
    
    #1. 첫 집을 터는 경우
    dp1[0] = money[0]
    dp1[1] = max(money[0],money[1]) 
    
    #2. 첫 집을 털지 않는 경우  
    dp2[0] = 0
    dp2[1] = money[1]
    
    for i in range(2,len(money)-1): # 마지막집은 계산에서 제외해야함
        dp1[i] = max(dp1[i-2]+money[i] , dp1[i-1])
    
    for i in range(2,len(money)):    
        dp2[i] = max(dp2[i-2]+money[i] , dp2[i-1])
     
    
    return max(max(dp1),max(dp2))

 

풀이

 

이전에 이코테 책을 풀면서 비슷한 dp문제를 만났어서 문제의 접근 자체는 어렵지 않았다.

i번째 집까지 털 수 있는 돈의 최대값을 dp[i]라고 할 때, 이웃한 집을 연속으로 털 수 없다면

i-2번째 집과 i집을 터는 선택지와 i-1번째 집을 털고 i번째 집을 털지 않는 선택지가 있다. 

이를 토대로 점화식을 세우면 

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

 

하지만 이 문제에서는 변수가 하나 있는데, 바로 집의 배치가 원형 구조로 첫 집과 끝 집이 이어져 있다는 것이다. 

다시 말해서 만약 첫 집을 턴다면 마지막 집을 털 수 없고, 마지막 집을 털었다면 첫 집은 털 수 없다는 것임

그걸 고려해서 두 가지 상황에 대한 결과를 따로 저장하고, 가장 큰 값을 찾으면 된다. 

 

1. 첫 번째 집을 털 경우

마지막 집에 대해서는 dp를 구하지 않아야 하므로(털지 않아야 하니까) for문의 범위를 len(money)-1 로 설정

 

2. 첫 번째 집을 털지 않을 경우

첫 번째 집에 대한 dp. 즉 dp[0] = 0이어야 한다. 

나는 처음 접근할 때 '그럼 dp[0] = money[-1] 이런 식으로 해야하나?' 하는 고민을 했었는데, 그럴 필요가 없다.

첫 번째 집을 털지 않는다고 해서 무조건 마지막 집을 털 수 있는 것은 아니므로, 

for문을 마지막 집까지 돌리면 어차피 점화식에 의해 마지막집을 털지말지는 알아서 최대값에 따라 결정이 됨

 

 

자바코드

import java.util.*;

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

 

 

파이썬 코드를 대부분 자바문법으로 변환하는 것이 다였는데, max()함수와 관련하여 마지막 부분에서 난관이 있었다.

보통 min이나 max함수를 사용할 때 파이썬에서는 배열 하나를 인자값으로 넣으면 배열의 원소 중 가장 큰 값을 반환하며 인자값으로 2개 이상의 변수를 넣을 수도 있다. 

하지만 자바에서 사용하는 Math.max() 및 Math.min() 함수는 인자값으로 항상 2개의 파라미터만을 받는다. 

그래서 for문을 돌려가며 dp중 가장 큰 값을 저장하는 로직을 따로 구현하는 방법을 사용해야 했는데, 

나는 stream을 사용해서 구현했다.