[백준 2156번] 포도주 시식

https://www.acmicpc.net/problem/2156

 

package dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DP2156 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] podo = new int[N + 1];
        int[] dp = new int[N + 1];

        for (int i = 1; i < N + 1; i++) {
            podo[i] = Integer.parseInt(br.readLine());
        }

        dp[1] = podo[1];
        if (N > 1) {
            dp[2] = podo[1] + podo[2];
        }
        for (int i = 3; i < N + 1; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 3] + podo[i - 1] + podo[i], dp[i - 2] + podo[i]));
        }

        System.out.println(dp[N]);


    }
}

 

OOX - dp[i-1] 

OXO - dp[i-2] + podo[i] 

XOO - dp[i-3] + podo[i] + podo[i-1]

 

이렇게 유추해서 구하면 되는 간단한 문제이다!!! 생각만 잘하면~~