티커 모으기 (2)

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

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

https://programmers.co.kr/learn/courses/30/lessons/12971

풀이 : DP 알고리즘을 통해 해당 위치에 따른 최대 점수를 구한다.

class Solution {
    public int solution(int sticker[]) {
        if (sticker.length <= 2) {
            int max = 0;
            for (int i = 0; i < sticker.length; i++) {
                max = Math.max(max, sticker[i]);
            }
            return max;
        }
        int [][] dp = new int [2][sticker.length];
		dp[0][0] = sticker[0];
		dp[0][1] = sticker[0];
		dp[1][1] = sticker[1];
		for (int i = 2; i < sticker.length; i++) {
			dp[0][i] = Math.max(dp[0][i-2] + sticker[i], dp[0][i-1]);
			dp[1][i] = Math.max(dp[1][i-2] + sticker[i], dp[1][i-1]);
		}
        return Math.max(dp[0][sticker.length-2], dp[1][sticker.length-1]);
    }
}