[프로그래머스-java] Lv.4 도둑질

알고리즘 : DP 

DP는 거의 아이디어 문제 인것 같다.

내 방식대로 풀고나서 다른 사람들의 블로그 글을 보았는데 솔직히 잘 이해 안되는 부분도 있었다.

하지만 내 방식은 그래도 이해하기 쉽지 않나? 싶다.

한번 천천히 읽어 보길 권장합니다.

사실 처음 풀어보는 Lv.4문제라서 겁먹었는데 생각만큼은 아니였다.

---

문제설명

링크참조

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

프로그래머스

---

내 풀이

 

우선 코드에 해당 설명의 주석을 달아 놓았다.혹시 모르거나 피드백할 부분 있으면 답글 부탁드립니다.

 

처음으로 연상할 수 있는 것은 집이 3개 있을 경우가 제일 편하다.

그러면 여기서 2가지 분기로 나뉜다.

첫번째 집을 선택할 경우와 선택하지 않을 경우

 

선택할 경우는 마지막 집을 선택하지 못하고 끝이난다.

선택하지 않을 경우는 마지막 집과 두번째 집중 최댓값이 나머지 값일 것이다.

그렇구나 생각하고 5개 집이 있는 경우로 넘어가자.

그림을 그려서 생각해보는 게 이런 문제는 연상이 쉽게 되는 것 같다.

첫번째 집을 선택한 경우

 

첫번째 집을 선택한 경우를 생각해보자

그림과 같이 첫번째 집을 선택한다면 1,2,3집은 dp값이 정해진다.

두번째집은 인접하므로 첫번째집 값으로, 세번째는 본인 값 + 첫번째 집값이 된다.

이제 핵심은 4번째 부터인데 4번째 집은 첫번째 집이 선택되었음으로 무조건 인접한 세번째 집선택 자체가 안된다.

당연한 소리 아니야 ? 맞다 하지만 계속 보자.

결국 4번째 값은 1,2번 값들 중 최고값과 본인 값을 더한 값으로 갱신하며 끝이난다.

마지막 집은 고려하지않는다.첫번째 집을 선택하면 마지막 집은 선택이 되지 않기 때문이다.

즉 첫번째집을 선택한 경우 전전집의 dp값(i-2), 전전전집의 dp값(i-3) 둘 중 큰값과 현재 집의 값을 더한 값이 되는 것이다.

식 : dp[i] = money[i] + max(dp[i-2],dp[i-3]) 

첫번째 집을 선택 안한경우

 

첫번째 집을 선택하지 않는 경우는 첫번째집의 값이 0, 두번째는 본인인 두번쨰 집 값일 것이고

세번째 부터 달라진다. 위 그림의 첫번째집을 선택했을 경우를 보면 무조건 인접한 세번째 값은 신경도 쓰지 않았다.

왜냐하면 무조건 1,3조합이 default값이였기 때문이었다. 하지만 이번에는 고려한다. 세번째 값이 예를 들어서 5라면 

두번째 값인 10을 선택하는 편이 더 좋기 때문이다.

위 그림 상으론 1번을 고려하는 것 처럼 되어 있어서 헷갈릴수도 있다.

하지만 20입장에서 다시보면 20 입장에선 본인과 10을 더해서 30을 하는 것보다 이전 집의 dp값을 취하는게 더 이득이다.

이처럼 첫번째 집을 선택하지 않는 다면 이전집의 dp값과 (현재 본인집 값 + 전전집의 dp값 ) 중 맥스값을 취하면 되는 일

 

근데 여기서 주의해야할건 첫번째 집을 선택하지 않는다고해서 항상 마지막 집은 필수가 아니라는 점이다.

말그대로 첫번째 집을 선택하는 경우와 안선택하는 경우 2가지인것이다

마지막 집은 상황에따라 선택될수도 안될수도있다.

 

이해가 안됬으면 설명이 부족한 것이므로 미안합니다 ㅜㅜ

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int N = money.length;
        int[] dp1 = new int[N];
        int[] dp2 = new int[N];
        
        // 첫번째 집 선탟 3번째까지 정해짐 
        dp1[0] = money[0]; dp1[1] = money[0]; dp1[2] = money[0] + money[2];
        // 첫번째 집 선택 안하는 경우는 2번째까지만 정해짐 
        dp2[0] = 0 ; dp2[1] = money[1];
        // 첫번째 집을 선택한 경우, 마지막 집 선택불가 
        // i-2번째 까지 합과 i-3번째 까지 합중 비교해서 MAX값을 현재값에 더해야된다.
        for (int i = 3 ;i <N-1;i++){
            dp1[i] = money[i] + Math.max(dp1[i-2],dp1[i-3]);
        }
        // 첫번째 집을 선택하지 않는 경우는 선택을 해야한다.
        // i-1 값과 i-2 + 현재값을 비교해서 큰값을 선택한다.
        for (int i = 2; i< N;i++){
            dp2[i] = Math.max(dp2[i-1],money[i] + dp2[i-2]);
        }
        // 최종적으로 값 비교후 정답 출력 
        int answer = 0;
        for (int i = 0; i<N;i++){
            if (answer < dp1[i]) answer = dp1[i];
        }
        for (int i = 0; i<N;i++){
            if (answer < dp2[i]) answer = dp2[i];
        }
        return answer;
    }
}