백준 2156(JAVA)

문제

풀이

이 문제는 dp문제로, 바텀업(반복문)을 통한 메모이제이션으로 풀수 있습니다.
큰 문제를 작은문제로 나누는데 항상 결과가 같기 때문입니다.(반대로 큰문제를 풀기위해 작은문제를 사용하는 것이 문제가 없다라고 생각해도 좋습니다.)
무슨말이냐면, 미지의 번호인 i번째에 포도주를 먹는데 i - 1, i - 2 ...이전의 포도주를 먹는 최대값이 사용될수 있다는 의미입니다.

저는 항상 dp문제를 보면 미지의 번호인 i번째의 최대값을 구하는데 어떤 이전의 값들이 사용될까를 생각합니다.

이 문제는 '연속된 세개의 포도주를 먹을수 없다'라는 제한조건만 잘생각해보면 됩니다.

i - 3	i - 2	i - 1	i
	안먹음	먹음	먹음
		안먹음	먹음
			안먹음

그렇다면 이런식으로 세가지 경우로 나눌수 있습니다.
표에 입력하지 않은 칸들은 이미 최대값들로 dp 테이블에 저장이 되어있다고 가정합니다.

그렇다면 i번째까지 먹은 최대의 포도주 값을 구할수 있습니다.

코드

package baekjoon.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;

public class Main2156 {
    static int n;
    static int[] drinks;
    static int[] dp = new int[10001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        drinks = new int[n + 1];
        for(int i = 1; i <= n; i++){
            drinks[i] = Integer.parseInt(br.readLine());
        }

        if(n >= 3){
            dp[1] = drinks[1];
            dp[2] = dp[1] + drinks[2];
            dp[3] = Math.max(dp[2], dp[1] + drinks[3]);
            for(int i = 3; i <= n; i++){
                int a = dp[i - 3] + drinks[i - 1] + drinks[i];
                int b = dp[i - 2] + drinks[i];
                int c = dp[i - 1];
                int max = IntStream.of(a, b, c).max().getAsInt();
                dp[i] = max;
            }
        }else if(n == 1){
            dp[n] = drinks[1];
        }else if(n == 2){
            dp[n] = drinks[1] + drinks[2];
        }

        System.out.println(dp[n]);
    }
}