스티커 모으기(2)

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

dp 동적계획법 코테

[0] [1] ... [i-2] [i-1] [i] ...

에서 i번 째 스티커를 뜯을 수 있는 경우는

i-1번 째 스티커를 뜯지 않아야 한다.

다시 말하면, [i-2]까지 누적된 최댓값에 해당 i번 째 스티커를 더해준다.

즉, dp[i] = dp[i-2] + sticker[i]

그리고, i번 째 스티커를 뜯지 않을 수 있으므로 

dp[i] = dp[i-1]도 고려해줘야한다.

import java.io.*;
import java.util.*;
 
public class Solution {
 
    static BufferedReader br;
    static BufferedWriter bw;
    
    static int[] dp, dp2;
    
    static int solution(int sticker[]) {
        int answer = 0;
        int len = sticker.length;
        
        if(len == 1) {
            return sticker[0];
        }
        else if(len == 2) {
            return Math.max(sticker[0], sticker[1]);
        }
        
        dp = new int[len+1]; // 첫 번째를 뜯었을 때 → 맨 마지막 스티커(len - 1)는 못 뜯는다. 그래서 31번 째 조건문을 추가해준다.
        dp2 = new int[len+1]; // 첫 번째를 안 뜯었을 때
        
        dp[0] = dp[1] = sticker[0];
        
        dp2[0] = 0;
        dp2[1] = sticker[1];
        
        for(int i=2; i<len; i++) {
            if(i != len - 1) dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]);
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i]);
        }
 
        return Math.max(dp[len - 2], dp2[len - 1]);
    }
 
    public static void main(String[] args) throws IOException  {
        // TODO Auto-generated method stub
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int[] sticker = {14, 6, 5, 11, 3, 9, 2, 10};
        
        System.out.println(solution(sticker));
    
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}
 
class pair {
    int first, second;
    pair(int a, int b) {
        this.first = a;
        this.second = b;
    }
}
 
class tuple {
    int first, second, third;
    tuple(int a, int b, int c) {
        this.first = a;
        this.second = b;
        this.third = c;
    }
}
 
class PQ implements Comparable<PQ> {
    int first, second;
    
    PQ(int f, int s) {
        this.first = f;
        this.second = s;
    }
    
    public int compareTo(PQ p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
        }
        
        return 1; 
        // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다.
        // -1로 하면 결과가 이상하게 출력됨.
    }
}