[Algo] 프로그래머스 스티커 모으기(2)

코드

import java.util.*;
class Solution {
    public int solution(int sticker[]) {
        int len=sticker.length;
        int[]frist=new int[len+1];
        int[]second=new int[len+1];

        if(len==1){
            return sticker[0];
        }
        int[]tmp=Arrays.copyOf(sticker,len);
        tmp[len-1]=0;
        frist[0]=tmp[0];
        frist[1]=Math.max(frist[0],tmp[1]);
        for(int i=0; i<len-2; i++){
            frist[i+2]=Math.max(frist[i+1], frist[i]+tmp[i+2]);
        }

        for(int i=0; i<len-1; i++){
            tmp[i]=sticker[i+1];
        }
        tmp[len-1]=0;
        second[0]=tmp[0];
        second[1]=Math.max(second[0],tmp[1]);
        for(int i=0; i<len-2; i++){
            second[i+2]=Math.max(second[i+1], second[i]+tmp[i+2]);
        }

        return Math.max(frist[len-1],second[len-1]);
    }
}

풀이

문제는 일차원 배열의 처음과 끝을 연결해 원형을 만들었음을 명시했지만, 맨 처음과 끝의 스티커를 관리하는 로직을 따로 추가해준다면 직선과 같이 풀 수 있다. 현재값(i)에서 가질 수 있는 가장 큰 값은

• 전칸에서 스티커를 뽑아서 현재 칸은 뽑을 수 없는 경우
• 전칸에서 스티커를 뽑지 않아서 현재 칸을 뽑을 수 있는 경우, 2전칸+현재칸을 뽑았다.

를 비교하면 알 수 있다.

식으로 쓴다면

• dp[i]=dp[i-1]
• dp[i]=dp[i-2]+sticker[i]

이다.

1번 스티커를 뽑는다면 마지막 스티커를 쓸 수 없고, 1번 스티커를 뽑지 않는다면 마지막 스티커를 사용할 수 있다. 1번 스티커의 유무는 배열의 값이 달라지는 결과를 낳기 때문에 따로 dp를 만들어주었다.

따라서 위의 두 가지 경우 * 스티커의 시작점 두 가지를 모두 DP로 계산해주면 된다!