Lv 4. 도둑질

 

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

프로그래머스

 

고민했던 흔적

 

 

이전에 한번 풀어본 유형의 DP 유형이었기에 쉽게

풀이할 수 있었다.  첫집과 끝집은 연결되어 있기 때문에

dp 배열을 2가지 종류로 나누어야했는데,

 

dp1은 첫집을 포함하는 경우로서 마지막 집의 포함경우를 제외하였고

dp2는 첫집을 포함하는 경우를 제외하는경우로서 마지막집의 돈을 포함한 결과이다.

 

결국 dp[0]은 0으로 설정해 주고 Math.max 함수를 통해

dp[i] = Math.max(dp[i-1],dp[i-2]+dp[i]) 라는 점화식을 세워

풀이할 수 있었다.

 

LV 4. 치곤 풀만한 문제였다.

 

 

import java.util.*;

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