[백준] 2156 포도주 시식 - Dynamic Programming / Java

• 문제 링크

2156번: 포도주 시식

 

• 풀이 과정

포도주의 정보를 입력받을 배열 wine 과 포도주의 양의 값을 누적할 dp 배열을

포도주의 개수 n + 1 만큼의 크기로 생성한다.

 

dp[1] 의 값은 포도주를 한잔만 마셨으므로 wine[1] 의 값으로 초기화,

dp[2] 의 값은 wine[1] + wine[2] 의 값으로 초기화하되, n = 1 인 경우를 고려해 조건문을 건다.

 

현재 위치까지 누적된 포도주 양의 경우의 수는 연속으로 3잔을 마실 수 없는 조건에 의하여

O 는 포도주를 마시는 경우, X 는 마시지 않는 경우를 나타낼 때 OOX, OXO, XOO 의 3가지 경우의 수가 가능한데,

 

OOX 는 현재 잔을 마시지 않은 이전까지의 누적된 최대 값(dp[i - 1]),

OXO 는 현재 잔을 마시고 두 인덱스 전까지의 누적된 최대 값(dp[i - 2] + wine[i]),

XOO 는 현재 잔과 이전 잔을 마시고 세 인덱스 전까지 누적된 최대 값(dp[i - 3] + wine[i - 1] + wine[i]) 을 나타내며

2 ~ n 까지 각각의 인덱스마다 이 3가지 경우의 수를 비교하여 최대 값을 dp배열의 해당 인덱스에 저장한다.

 

이 후 모든 경우의 수를 비교한 결과 최대 값이 저장된 dp[n] 을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] wine = new int[n + 1];
        int[] dp = new int[n + 1];

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

        dp[1] = wine[1];

        if (n > 1)
            dp[2] = wine[1] + wine[2];

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

        bw.write(dp[n] + "\n");
        bw.flush();
    }

}