[Programmers] 스티커 모으기(2) (JAVA)

프로그래머스

 

풀이

 

첫번째 스티커를 뗐을 때와 두번째 스티커를 뗐을 때로 나눠서 DP를 구해주면 된다.

[1,2,3,4,5,6,7,8]이라는 스티커 모음이 있다고 가정했을 때

 

만약 첫번째 스티커를 사용하게 되면, 마지막 스티커는 사용할 수 없기 때문에

[1,2,3,4,5,6,7]을 사용해서 DP를 구해주면 된다.

 

그럼 두번째 스티커를 사용하게 되면? 첫번째 스티커를 사용할 수 없다.

[2,3,4,5,6,7,8]을 이용해서 DP를 구하면 된다.

 

첫번째 스티커를 뗐을 때는 dp0[0]=sticker[0] 첫번째 스티커의 숫자이다.

이후 2번째 스티커는 뗄 수 없기 때문에 dp0[0] = dp0[1]

3번째 스티커부터는 비교를 해줘야한다. 

이전 스티커의 숫자와, 전전까지 온 dp0[i-2]+현재스티커 숫자 중 큰 수가 남으면 된다.

 

두번째 스티커도 마찬가지!

 

DP는 항상 어렵다.................. :(

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        
        if(sticker.length == 1){
            answer = sticker[0];
            return answer;
        }
        int dp0[] = new int[sticker.length];
        //첫번째 스티커를 뗐을 때
        dp0[0] = sticker[0];
        dp0[1] = dp0[0];
        for(int i=2; i<sticker.length-1; i++){
            dp0[i] = Math.max(dp0[i-1], dp0[i-2]+sticker[i]);
        }
        answer = dp0[sticker.length-2];
        
        int dp1[] = new int[sticker.length];
        //두번째 스티커를 뗐을 때(첫번째 스티커를 안 뗐을 때)
        dp1[0] = 0;
        dp1[1] = sticker[1];
        for(int i=2; i<sticker.length; i++){
            dp1[i] = Math.max(dp1[i-1], dp1[i-2]+sticker[i]);
        }
        
        answer = Math.max(answer, dp1[sticker.length-1]);

        return answer;
    }
}