[프로그래머스 ,Java] Level3: 스티커 모으기

이 문제는 level 4 도둑질 문제다

 

문제분석

 

문제 이해는 매우쉽다.  요점은 한 지점을 골랏으면 양옆 지점을 못고른다.

 

이 규칙을 유지하면서  최대로 얻을수있는 스코어를 반환하면된다.

 

놀라운건 이 스티커문제와 도둑질문제 로직이 100%같다. (중복문제..)

 

 

이해는 쉽게했는데 막상 짜려고하면 참 막막할것이다.

DP를 짜는건 늘 새롭고 어렵다..

 

 

하나씩 생각해보자..

1.첫번째를 고르면   마지막과 두번째를 못고른다.

2.두번째를 고르면   첫번째 와 세번째를 못고른다.

 

이 2가지 경우가 명백하게 다른 결과를 나타내는걸 푸는 사람 모두가 동의할것이다.

 

 

1번루트를 한번 타보자.

예시 {14,6,5,11}

 

첫번째를 고르면  첫번째는 14이다.

두번째를 고르는건 불가능하다. -> 현재 까지 최고값인 14로 저장해두자.

 

세번째를 고를수도 있고 안고를수도있다.  -> 고르면 19 , 안고르면 25를 얻을수있음.

 

-> 이 세번째를 고르는 경우를 이렇게 짤수있다. dp[2] = Max(dp[1], dp[0]+dp[2])

즉,  본인의 위치 -1값은 자신을 안뽑은것과 마찬가지다. (당연히 이웃이 뽑히면 난 안뽑히니깐!)

또한, 본인의 위치 -2값은 자신을 뽑은 경우이다.

 

이 두값을 비교하면, 고른경우와 안고른경우중 젤 높은값을 판별이가능하다.

 

2번 루트를 타보자.

예시 {14,6,5,11}

 

첫번째는 못고른다.  못고르니깐 0이다.

두번째를 고른다. 골랏으니 6이다.

세번째는 못고른다  아까 쓴 dp[2]= Max(dp[1],dp[0]+dp[2]) 를 사용하면  6이나온다.

네번째는 고를수있다.  dp[3] = Max(dp[2],dp[1]+dp[3])을 사용하면 17이 나온다.

 

 

1번과 2번루트를 돌았는데 결과가 역시 다르게 나온다.

 

그렇다면 마지막에 Max(1번루트,2번루트)를 하면 된다.

 

 

전체풀이

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
 
        int len = sticker.length;
 
        if (len == 1) return sticker[0];
 
        int[] dp1 = new int[len];
        int[] dp2 = new int[len];
 
        //첫번째 스티커를 떼는 방법
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];     
    
        //두번째 스티커를 떼는 방법
        dp2[1] = sticker[1];
        for (int i = 2; i < len; i++){
            dp1[i] = Math.max(dp1[i-1],dp1[i-2] + sticker[i]);
            dp2[i] = Math.max(dp2[i-1],dp2[i-2] + sticker[i]);
        } 
 
        answer = Math.max(dp1[len-2],dp2[len-1]);
 
        return answer;
    }
}

 

 

DP문제는 늘 다이아몬드를 세공하는 느낌이다.

 

DP의 규칙찾는건 엄청난 노고가 드는데, 막상 결과물로 나오는 로직은 매우 간단해보이고 아름답기때문이다..