[Programmers] 스티커 모으기

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

일반적인 DP문제랑 조금 다른 점이 있다면 스티커가 원형으로 연결되어 있다는 점이다. 원형으로 연결되어서 첫번째 스티커를 고르면 마지막 스티커를 못고르는데 DP를 한줄로 진행하게 되면 첫번째 스티커를 골랐는지에 대한 정보가 없어 마지막 스티커에서 선택할 수가 없다.

풀이 설명

1. 스티커가 3개 이상임을 전제로 DP를 사용하기때문에 스티커가 2개 이하일때 예외처리를 해준다.
2. cache 배열을 2행으로 만들어서 0행은 첫번째 스티커를 선택하지 않는 경우, 1행은 첫번째 스티커를 선택하는 경우로 나눠서 DP를 진행한다.
3. DP를 완료하고 두 경우 중 더 높은 값을 반환한다.

코드

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;

        int n = sticker.length;

        // n<=2일때 예외처리
        if (n == 1)
            return sticker[0];
        if (n == 2)
            return Math.max(sticker[0], sticker[1]);

        // 메모이제이션 배열
        // 0행은 첫번째 스티커를 선택하지 않는 경우, 1행은 첫번째 스티커를 선택하는 경우
        int[][] cache = new int[2][n];

        // 시작 부분
        cache[0][0] = 0;
        cache[0][1] = sticker[1];
        cache[1][0] = sticker[0];
        cache[1][1] = sticker[0];
        // DP 진행
        for (int i = 2; i < n - 1; ++i) {
            cache[0][i] = Math.max(cache[0][i - 2] + sticker[i], cache[0][i - 1]);
            cache[1][i] = Math.max(cache[1][i - 2] + sticker[i], cache[1][i - 1]);
        }
        // 끝 부분
        cache[0][n - 1] = Math.max(cache[0][n - 3] + sticker[n - 1], cache[0][n - 2]);
        cache[1][n - 1] = cache[1][n - 2];

        // 두 케이스 중 더 높은 값을 반환
        answer = Math.max(cache[0][n - 1], cache[1][n - 1]);
        return answer;
    }
}