[백준] 2156 포도주 시식 자바(Java)

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

2156번: 포도주 시식

가장 많이 마실 수 있는 상황의 값을 저장한 dp 테이블

int[] dp = new int[n + 1];

와인의 용량이 저장된 테이블

int[] values = new int[n + 1];

 

와인을 마실 수 있는 경우의 수

아래 그림 3가지 중 가장 큰 값이 dp[i] 에 저장이 된다.

현재 i위치에 있는 와인을 마시는 경우 그림에서 위에 2줄

연속으로 3잔을 모두 고를 수 없다는 것을 고려한다.

1. n-1 잔을 마신경우 n-2 잔을 고를 수 없다.

2. n-1 잔을 마시지 않은 경우 n-2n-2 잔을 고를 수 없다. -> n - 3 잔 선택

여기서 n-2, n-3잔을 선택하는 경우에는 누적값을 더하게 된다. -> 최대 합의 값을 구해야 하기 때문!

 

누적값 초기화

dp[1] = values[1];
if (n > 1) {
    dp[2] = values[1] + values[2];
}

 

Math.max(dp[i-2], dp[i-3] + values[i-1]) + values[i]

현재 i위치에 있는 와인을 마시지 않는 경우 그림에서 맨 마지막 줄

dp[i - 1]

 

현재 위치에서 가장 많이 마실 수 있는 상황의 값 dp [ i ]는

dp[i] = Math.max(dp[i-1], Math.max(dp[i-2], dp[i-3] + values[i-1]) + values[i]

 

자바 코드

package main.iyk2h;

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] values = new int[n + 1];
        int[] dp = new int[n + 1];

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

        dp[1] = values[1];
        if (n > 1) {
            dp[2] = values[1] + values[2];
        }

        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2], dp[i - 3] + values[i - 1]) + values[i]);
        }

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