[lv3] 스티커 모으기(2)

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

 

1. dp 배열의 설정

dp[i][Y] - i번째 스티커를 떼어냈을 때 최댓값

dp[i][N] - i번째 스티커를 떼지 않았 때 최댓값

 

2. 뽑는 경우의 수는 2가지 [o x o], [o x x o]

후자의 경우를 위해, i-2번째 까지 고려

 

 

3. 점화식 세우기

 

3-1. dp[i][Y] = Math.max(dp[i-1][N], dp[i-2][Y]) + sticker[i];

dp[i-1][Y] => 불가능
dp[i-2][N] => 항상 dp[i-2][Y] > dp[i-2][N] 이므로 고려할 필요 X

3-2. dp[i][N] = Math.max(dp[i-1][Y],  dp[i-2][Y]]);

dp[i-2][N] => 항상 dp[i-2][Y] > dp[i-2][N] 이므로 고려할 필요 X
dp[i-1][N] => 항상 dp[i-1][Y] > dp[i-1][N] 이므로 고려할 필요 X

 

4. 원형 dp의 처리 - 시작과 끝은 이어져 있음

 

4-1. dp[0][Y] = sticker[0]; 으로 설정했을 경우

dp[마지막][Y] => 불가능

dp[마지막][N] => 가능

 

4-2. dp[0][Y] = 0; 으로 설정했을 경우

dp[마지막][Y] => 가능

dp[마지막][N] => 가능

 

두 가지 경우에 대해 tryDp()한다.

 

--------------------------------------------------------------------

 

원형 DP를 처리하는 방법에 대해 탐구한 것은 3가지다.

arr = [1,2,3,4,5,6] 이라면,

 

1.초기값 설정(dp[0] = 1) 여부에 따라 끝 값을 별도 처리 한다.

=> 본문에서 사용

 

2. [1,2,3,4,5,6], [6,1,2,3,4,5] 두 가지 경우로 탐색한다.

import java.util.*;
class Solution {
    
    static int N, Y=1;
    public int solution(int sticker[]) {
        int answer = 0;
        
        int dp[][] = new int[sticker.length][2];
        dp[0][Y] = sticker[0];
        answer = tryDp(sticker, dp);
        
        int dp2[][] = new int[sticker.length][2];
        int[] sticker2 = new int[sticker.length];
        
        for(int i=0; i<sticker2.length-1; i++) {
            sticker2[i+1] = sticker[i];
        }
        sticker2[0] = sticker[sticker.length-1];
        
        dp2[0][Y] = sticker2[0];
        
        answer = Math.max(answer, tryDp(sticker2, dp2));
        
        return answer;
    }
    
    public int tryDp(int sticker[], int dp[][]) {
        int max = 0;
        int s = sticker.length-1;
        for(int i=1; i<=s; i++) {
            
            if(i < 2) {
                dp[i][N] = dp[i-1][Y];
                dp[i][Y] = sticker[i];
            }
            else if(i==s) {
                dp[i][N] = Math.max(dp[i-1][Y], dp[i-2][Y]);
            }
            else {
                dp[i][N] = Math.max(dp[i-1][Y], dp[i-2][Y]);
                dp[i][Y] = Math.max(dp[i-2][Y], dp[i-2][N]) + sticker[i];
            }
        }

        return Math.max(dp[s][N], dp[s][Y]);
    }
}

 

3. [1,2,3,4,5], [2,3,4,5,6] 두 가지 범위로 나누어 대해서만 탐색한다.

=> 이런 방법이 있구나 싶었다.

https://school.programmers.co.kr/questions/77264

 

class Solution {

    static int N, Y=1;
    public int solution(int sticker[]) {
        int answer = 0;

        int dp[][] = new int[sticker.length][2];
        answer = tryDp(sticker, dp, false);

        dp = new int[sticker.length][2];
        dp[0][Y] = sticker[0];
        answer = Math.max(tryDp(sticker, dp, true), answer);

        return answer;
    }

    public int tryDp(int sticker[], int dp[][], boolean dtch) {

        int s = sticker.length-1;
        for(int i=1; i<=s; i++) {

            if(i == 1) {
                dp[i][N] = dp[i-1][Y];
                dp[i][Y] = sticker[i];
            }

            else if(i == s) {
                if(dtch) {
                    dp[i][N] = Math.max(dp[i-1][Y], dp[i-2][Y]);
                }
                else {
                    dp[i][N] = Math.max(dp[i-1][Y], dp[i-2][Y]);
                    dp[i][Y] = Math.max(dp[i-1][N], dp[i-2][Y]) + sticker[i];
                }
            }

            else {
                dp[i][N] = Math.max(dp[i-1][Y], dp[i-2][Y]);
                dp[i][Y] = Math.max(dp[i-1][N], dp[i-2][Y]) + sticker[i];
            }
        }

        return Math.max(dp[s][N], dp[s][Y]);
    }
}