[백준_2156번] 포도주 시식

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

2156번: 포도주 시식

[문제]

 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

 

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

 

[입력 조건]

 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

 

[코드]

import java.util.*;

public class BaekJoon_2156 {
	public static int n;
	public static int[] wine; 
	public static Integer[] dp; 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		wine=new int[n+1];
		dp=new Integer[n+1];
		
		for(int i=1;i<=n;i++)
			wine[i]=sc.nextInt();
		
		dp[0]=0;
		dp[1]=wine[1];
		
		/*
		 * n이 1인 경우는 처음 와인의 양이 최댓값이고
		 * n이 2 이상인 경우의 dp[2]는 wine[1]+wine[2]이 항상 최댓값이다.
		 */
		if(n>1)
			dp[2]=wine[1]+wine[2];
		
		System.out.println(choose(n));
	}
	
	/*
	 * dp는 이전 잔들을 선택 한 최대 합을 의미한다.
	 * 해당 문제의 특징은 마지막 와인잔을 더했을 경우까지가 최대합이 될 수도 있고
	 * 그 이전까지의 합이 최대합이 될 수도 있다는 것이다.
	 * Math.max(choose(n-2), choose(n-3)+wine[n-1])+wine[n] 부분은 마지막 와인잔을 더했을 경우
	 * choose(n-1) 부분은 마지막 이전 와인잔 까지의 선택이 최대 누적합인 경우이다.
	 */
	public static int choose(int n) {
		if(dp[n]==null) {
			dp[n]=Math.max(Math.max(choose(n-2), choose(n-3)+wine[n-1])+wine[n],choose(n-1));
		}
		return dp[n];
	}
}

 

[고찰]

 이번 문제는 백준 2579 계단 오르기 문제와 흡사했다. 그래서 2579 문제와 같은 풀었지만 정답 처리를 받지 못해 이유가 무엇일까 생각해보았다. 결론은 마지막 와인잔을 무조건 마셔야 하냐 아니냐를 고려해야 한다는 것이었다. 마지막 와인잔을 무조건 마셔야 하는 경우와 마지막 와인잔의 이전 와인잔까지의 누적 합이 최대일 경우 이 두 가지를 비교해야 완벽한 정답 처리를 얻을 수 있다. 이러한 과정에서 3개 이상 연속된 와인잔을 마시지 못한다는 조건까지 고려를 해야 한다. 이 문제를 풀면서 돌아보니 아직 계단 오르기 문제도 완벽하게 이해하지 못한것 같아 복습하는 시간을 가졌다.