[DP] 백준 2156 포도주 시식 (Wine Tasting)

BackJoon 

# 2156 - 포도주 시식 (Wine Tasting)

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

대표적인 DP문제입니다.

연속으로 3번 마시지 않으면서 주어진 N개 포도주를 어찌어찌 마신다면, 얼만큼 마실 수 있느냐 그 최고 값을 찾아라 입니다.

어찌어찌 마신다는 것은 우리가 어떻게 마셔라 라고 마음대로 정해줄 수 있다는 뜻입니다. 

3번 연속으로 마실 수 없다는 것을 따져보면, 0번 연속 마실 수 있는 경우, 1번 연속 마실 수 있는 경우 , 2번 연속 마실 수 있는 경우가 있습니다.

자 그럼 점화식을 짜봅시다.ㅎㅎㅎㅎ

dp[n] = 포도주 n개가 주어졌을 때, 가장 많이 마실 수 있는 양

p[n] = n번째 포도주의 양

0번 연속 마실 수 있는 경우

n번째 포도주를 0번 마실 경우 n-1의 포도주는 마셔도 되고 안 마셔도 되고 그러니까 그냥 dp[n-1]의 값이 n번째 포도주를 0번 연속 마셨을 경우랑 같습니다.

dp[n] = dp[n-1]

1번 연속 마실 수 있는 경우

n번째 포도주를 1번 연속 마실 수 있는 경우가 되기 위해선 n-1 번째 포도주는 마시면 안됩니다. 마시면 n번째 포도주는 2번 연속 마시게 되는 경우가 되니까요. 그래서 n-1 번째 있는 포도주는 마시면 안됩니다. 그 다음 n-2 번째 있는 포도주는 마셔도 될까요? 안마셔도 될까요? 네 맞습니다. 상관없어요 이미 n-1번째 포도주를 안 마신 것으로도 n번째 포도주가 1번 연속 마실 수 있는 경우를 만족하니까요. 그렇다면 다음 과 같은 식이 완성됩니다.ㅎㅎ

dp[n] = dp[n-2]+p[n]

2번 연속 마실 수 있는 경우

자 마지막으로 n번 포도주가 2번 연속으로 마셨을 경우입니다. 당연히 2번 연속이니까, n-1 포도주는 마셔야 합니다. 자 그다음 n-2번째는 마셔야 할까요? 안 마셔야 할까요? 네 맞습니다. 안마셔야겠죠. n번째 포도주가 2번 연속으로 마셨을 경우가 충족 돼야 하기 때문이죠 ㅎㅎ 그 다음 n-3번째 포도주는 마셔야 할까요? 안 마셔야 할까요? 네 상관없습니다. 그렇다면 다음과 같은 점화식이 완성됩니다!

dp[n]  = dp[n-3]+p[n-1]+p[n]

여기서 잠깐 완성된 3가지 점화식을 보면, n-3 첨자가 있습니다. 이 값을 처리하기 위해서 n 은 3부터 시작하게 합니다.

또한, n=1인 경우 n=2인 경우는 초기화 시켜 예외처리 해줘야 문제가 발생되지 않습니다. (코드상에서는 n은 i이고, 코드상에 있는 n은 그냥 주어진 포도주 잔 개수입니다.)

이를 코드로 옮겨보면 다음과 같습니다.

package BackJoon;

import java.util.Arrays;
import java.util.Scanner;

public class WineTasting {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int p[] = new int[n+1];
		int dp[] = new int[n+1];
		
		for(int i=1; i<=n; i++){
			p[i] = sc.nextInt();
		}
		//점화식에서 i-3까지 가기때문에 1,2는 편의상 초기화 해준다.
		dp[1] = p[1];
		if(n > 1) // 1인 경우 터지기 때문에 예외처리
		dp[2] = p[1] + p[2];		
		for(int i=3; i<=n; i++){
			//연속 0 번 마신경우 	//연속 1번 마신경우 //연속 2번마신 경우
			dp[i] = Math.max(dp[i-1],Math.max(dp[i-2]+p[i],dp[i-3]+p[i-1]+p[i]));

		}
		
		System.out.println(dp[n]);
		
		

	}

}