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

Summer/Winter Coding(~2018)

---

스티커 모으기(2)

---

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

코딩테스트 연습 - 스티커 모으기(2)

 

전형적인 DP 문제라고 생각했는데, 원형으로 이어져 있는 부분이 생각보다 까다로운 포인트였다.

백준의 사회망서비스(SNS)와 비슷한 문제로, DP로 해결할 수 있다.

public class 스티커모으기2 {
	public static void main(String[] args) {
		System.out.println(solution(new int[] { 14, 6, 5, 11, 3, 9, 2, 10 }));
	}

	public static int solution(int sticker[]) {
		int len = sticker.length;
		if (len == 1) {
			return sticker[0];
		}
		int[][] dp = new int[2][len];
		dp[0][0] = sticker[0]; // 처음 스티커 떼는 경우의 수
		dp[0][1] = sticker[0];
		dp[1][0] = 0; // 처음 스티커 안 떼는 경우의 수
		dp[1][1] = sticker[1];
		for (int i = 2; i < len; i++) {
			dp[1][i] = Math.max(dp[1][i - 2] + sticker[i], dp[1][i - 1]);
			if (i == len - 1) {
				break;
			}
			dp[0][i] = Math.max(dp[0][i - 2] + sticker[i], dp[0][i - 1]);
		}
		return Math.max(dp[0][len - 2], dp[1][len - 1]);
	}

}