백준 2156번 포도주 시식 S1 - DP

맛있는 와인 마시고 싶다.

 

 

효주도 와인이 마시고 싶었나 보다.

되도록이면 많이

DP로 최대한 많이 마실 수 있는 양을 찾아줍시다.

3잔 연속으로 못마시므로

이전 와인을 마시게 된다면 idx - 3에서의 최대값을 써야겠죠

 

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {// Boj_2156_포도주 시식
    // DP
    public static int N;
    public static int[] dp, arr;
    // 잔 마시고 제 위치.
    // 3잔 연속 불가능
    // 최대한 많은 양이 많게
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        dp = new int[Math.max(3, N + 1)];
        arr = new int[Math.max(3, N + 1)];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        // 이전 와인을 마시는게 이득인지 구분
        // 이전 와인을 마시면 dp i-3 을 사용해야함
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        // dp[i] = dp[i-1] 이랑 dp[i-2] + arr[i], dp[i-3] + arr[i] + arr[i-1]
        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1]));
        }
        System.out.println(dp[N]);
 
    }
}
 

 

간단쑤