[백준 - Java] 2156번 : 포도주 시식

문제

www.acmicpc.net/problem/2156

2156번: 포도주 시식

설명

백준 2597번 계단 오르기와 비슷하게 DP (Dynamic Programing) 동적 계획법으로 풀 수 있는 문제다.

 

[백준 - Java] 2579번 : 계단 오르기

 

하지만 계단 오르기완 다르게 하나 더 고려할 점이 있다.

바로 와인을 먹지 않는 경우 역시 고려해야 한다는 것이다.

 

일단 그 경우를 제외하고 생각해보자. 

 

먼저 와인은 3잔 연속 먹을 수 없다.

따라서 현재 와인을 먹을 수 있는 경우는

1. 전 와인을 먹고 현재 와인을 먹거나,

2. 전전 와인을 먹고 현재 와인을 먹는 2가지 경우로 나눌 수 있다.

이 두가지 경우 중 더 큰 값(더 많이 와인을 마시는 양)을 dp 배열에 저장하며 최대로 마실 수 있는 와인의 양을 구하는 것이다.

 

dp [n]은 n번째 와인까지 따졌을 때 마실 수 있는 와인의 최대 양이될 것이고, 각 경우는 아래와 같이 나타낼 수 있다.

1. 전전전(n-3)까지의 최대 양 + 전(n-1) 번째 양 + 현재 양 = (dp [n-3] + wine [n-1] + wine [n])

2. 전전(n-2)까지의 최대 양 + 현재 양 = (dp [n-2] + wine [n])

 

문제의 예시 [6, 10, 13, 9, 8, 1]에서 최종 저장된 dp값을 살펴보면 [6, 16, 23, 28, 33, 32]와 같이 저장이 된다.

dp [6]에 저장되어야 하는 값은 32가 아니라 33이어야 한다.

 

하지만 1의 양을 가진 6번째 와인을 마셨기 때문에 32가 계산된 것이다.

즉, 이전까지 구한 dp값보다 현재 와인을 마심으로써 구한 dp값이 작다면 현재 와인을 마시지 말아야 한다.

 

따라서 기존 2가지 조건에 3. 전(n-1)까지의 최대양 + 현재 와인을 마시지 않는 경우도 추가해 같이 비교해주어야 한다.

전체 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[] wine = new int[n+1];
		for(int i = 1; i < n+1; i++) {
			wine[i] = sc.nextInt();
		}
		
		int[] dp = new int[n+1];
		dp[1] = wine[1];
		if(n > 1) { // N=1의 경우를 대비해 예외처리 
			dp[2] = wine[1] + wine[2];
		}
	
		for(int i = 3; i < n+1; i++) { // 전 와인과 전전 와인을 먹을 수 있는 3번째 와인부터 시작 
			dp[i] = Math.max(dp[i-1], Math.max(dp[i-2], dp[i-3] + wine[i-1]) + wine[i]); 
		}
		
		System.out.println(dp[n]);
	}

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%232156/src/Main.java

KwonMinha/BOJ