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

문제

2156번: 포도주 시식

 

 

알고리즘

다이나믹 프로그래밍 (DP)

 

 

풀이

연속으로 최대 2잔의 포도주만 마실 수 있기 때문에 특정 포도주를 마실 수 있어도 안마시는 것이 더 나은 경우가 있다.

따라서 연속으로 마신 포도주의 잔 수에 대한 최댓값을 기록한다.

 

[n + 1][3] 크기의 2차원 배열 dp를 선언하여 다음과 같이 저장하였다.

dp[i][j] = i 번째 포도주까지 연속 j 잔 마셨을 때 최대로 마실 수 있는 포도주의 양

 

dp[i][0] 은 i번째 포도주를 마시지 않은 경우이다.

dp[i][1] 은 i번째 포도주가 연속으로 마신 첫번째 포도주인 경우,

dp[i][2] 는 i번째 포도주가 연속으로 마신 두번째 포도주인 경우이다.

 

즉

dp[i][0] 은 이전 포도주를 마시지 않았거나, 연속 한 잔 마신 경우, 연속 두 잔 마신 경우 모두 상관없고,

dp[i][1] 은 이전에 포도주를 마시지 않은 경우,

dp[i][2] 는 이전에 포도주를 연속 한 잔 마신 경우에만 가능하다.

 

따라서 점화식은 다음과 같다.

dp[i][0] = Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
dp[i][1] = dp[i-1][0] + num;
dp[i][2] = dp[i-1][1] + num;

이때 num은 i번째 포도주의 양이다.

dp[i][0] 은 i번째 포도주를 마시지 않는 경우이므로 num을 더하지 않는다.

 

위와 같이 n번째 포도주까지 탐색을 진행한 후 dp[n][0] , dp[n][1] , dp[n][2] 중 최댓값을 출력한다.

 

 

코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		for (int i = 1; i <= n; i++) {
			int num = Integer.parseInt(br.readLine());

			dp[i][0] = Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
			dp[i][1] = dp[i-1][0] + num;
			dp[i][2] = dp[i-1][1] + num;
		}
		
		System.out.println(Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2]));
	}
}