[JAVA/백준] 동적 계획법 1: 포도주 시식

👀 문제

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

👊 도전

1. 설계

1. 연속해서 세 번 마시지 않는 방법은 OOX, OXO, XOO이다.
2. 셋 중 큰 값을 dp에 넣는 방식으로 구현한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;

/**
 * 
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] array=new int[n+1];
		for(int i=1;i<=n;i++){
			array[i]=input.nextInt();			
		}
		int[] dp=new int[n+1];
		
		dp[1]=array[1];
		if(n>1) dp[2]=dp[1]+array[2];
		
		for(int i=3;i<=n;i++){
			dp[i]=Math.max(dp[i-1], Math.max(dp[i-2]+array[i], dp[i-3]+array[i-1]+array[i]));
		}
		
		System.out.println(dp[n]);
	}
}
 

3. 결과

🤟 성공 🤟

4. 설명

1. DP를 이용한다.
   • array[]는 입력받은 포도주 양을 저장하고, dp[]에는 최대로 마신 양을 저장한다.
   • n==1일때 dp는 array[1]을, n==2는 array[1]+array[2]의 값을 가진다.
   • n>=3부터 for문을 통해 값을 넣는다. i-2, i-1, i 순서로 OOX, OXO, XOO가 가능하다.
   • OOX를 식으로 나타내면 dp[i]=dp[i-1]이다. 이전 잔을 마셔야하므로 i-1까지의 최대 잔을 가져오고, i는 마시지 않기 때문에 array[i]는 더하지 않는다.
   • OXO는 dp[i]=dp[i-2]+array[i]이다.
   • XOO는 dp[i]=dp[i-3]+array[i-1]+array[i]이다. i-2를 마시지 않기 때문에 이전까지의 누적값을 i-3에서 가져오고, i-1와 i를 연속해서 마셔야하므로 array[i-1], array[i]를 더한다.
   • 세 가지 경우의 수 중 Math.max()를 이용하여 최댓값을 택한다.

👏 해결 완료!

참고

• [DP] 백준 2156 포도주 시식 (Wine Tasting) https://limkydev.tistory.com/112
• [BOJ] 백준 2156 - 포도주 시식 (자바) https://zoonvivor.tistory.com/133