[백준] 포도주 시식 2156 - JAVA

문제

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

2156번: 포도주 시식

풀이

단순한 DP문제인줄 알았는데 한단계 더 생각해야 했던 DP문제다

dp[i] => i번째 잔까지 마실 수 있는 와인 최대 양

 

문제에서 연속으로 놓여 있는 3잔을 모두 마실 수는 없다고 한다. 따라서 경우의 수는 다음과 같이 나온다.

 

3번째 잔을 선택했다고 하자

1. <OOX>

와인순서	1	2	3	4	5	6	7
선택 여부	O	O	X

2. <OXO>

와인순서	1	2	3	4	5	6	7
선택 여부	O	O	X

3. <XOO>

와인순서	1	2	3	4	5	6	7
선택 여부	O	O	X

위 세가지 경우에 대한 식은 다음과 같다.

1. OOX : dp[i-1]
2. OXO : dp[i-2] + arr[i]
3. XOO : dp[i-3] + arr[i-1] + arr[i]

세 가지 경우 중 가장 max값을 dp[i]에 저장한다. 최종적으로 dp[n]에 저장되는 수가 마실 수 있는 와인의 최댓값이 된다.

 

코드

import java.util.*;
import java.io.*;

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 arr [] = new int [n+1];
		int dp [] = new int [n+1];
		
		for(int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		dp[1] = arr[1];
		if(n > 1)
			dp[2] = arr[1] + arr[2];
		
		
		for(int i = 3; i <= n; i++) {
			dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + arr[i], dp[i-3]  + arr[i-1] + arr[i]));
			
		}
		
		System.out.print(dp[n]);
	}
	
	   
}