프로그래머스 - 스티커 모으기(2) (feat. Java)

문제 정보는 아래 링크를 확인해주세요!

 

[스티커 모으기(2)]

프로그래머스

 

문제 접근 방법

• 첫 번째 생각해야할 것은 스티커를 선택하는 방법은 첫 번째를 선택하느냐, 선택하지 않느냐 이 두가지로 나뉜다.
• 두 번째는 현재 스티커와 현재-2 스티커를 선택했을 때의 결과와 인접 스티커를 선택했을 때의 결과중 최댓값을 구해준다.
• 이 방식은 DP 방식으로 푸는 것이 유리하므로, 점화식을 세우면 아래와 같다.
• DP[N] = MAX(DP[N-1], STICKER[N] +DP[N-2]); 

[소스 코드]

 

package algorithm.programmers;

import java.util.*;

/*
 * 2018 summer/winter conding
 * 스티커 모으기(2)
 * */
public class Pro12971 {

    public static 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];
        for (int i = 2; i < len-1;i++) dp1[i] = Math.max(dp1[i-1],dp1[i-2] + sticker[i]);


        //첫번째 스티커를 뗴지 않는 방법
        dp2[0] = 0;
        dp2[1] = sticker[1];
        for (int i = 2; i < len; i++) dp2[i] = Math.max(dp2[i-1],dp2[i-2] + sticker[i]);

        answer = Math.max(dp1[len-2],dp2[len-1]);

        return answer;
    }
}