135. 2156(포도주 시식)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] wine = new int[n];
		int[] wineDp = new int[n];

		for (int i = 0; i < n; i++) {
			wine[i] = sc.nextInt();
		}

		try {
			wineDp[0] = wine[0];
			wineDp[1] = Math.max(wine[0] + wine[1], wine[1]);
			wineDp[2] = Math.max(Math.max(wine[0] + wine[1], wine[0] + wine[2]), wine[1] + wine[2]);

			for (int i = 3; i < n; i++) {
				wineDp[i] = Math.max(Math.max(wineDp[i-1],wineDp[i-3] + wine[i-1] + wine[i]), wineDp[i-2] + wine[i]);
			}
		
			Arrays.sort(wineDp);
			
			System.out.println(wineDp[wineDp.length-1]);
			
		} catch (Exception e) {
			int sum = 0;
			for (int val : wine) {
				sum += val;
			}
			System.out.println(sum);
		}

	}
}

문제요약

연속해서 세잔은 마시는것이 불가능하다.

그때 제일 많이 시음할 수 있는 양은 얼마인가?

설명

전전 문제인 계단오르기와 비슷하지만, 계단은 꼭 그 곳을 밟아야 하지만 포도주는 해당 부분을 시음하지 않고 지나갈 수 있다.

그에 대한 예가 이것이다.

2000의 양을 시음하고 굳이 1의 양을 시음하는 것보다 시음하지 않고 넘어가 마지막 2000을 먹는 것이 더 최대로 먹을 수 있다는 뜻이다.

wineDp[0] = wine[0];
wineDp[1] = Math.max(wine[0] + wine[1], wine[1]);
wineDp[2] = Math.max(Math.max(wine[0] + wine[1], wine[0] + wine[2]), wine[1] + wine[2]);

index 2번 부터는 시음을 하지 않고 넘어가도 되는지에 대한 판단이 필요하다.

따라서 2번을 먹지 않은 경우 wine[0] + wine[1] 가 추가된 것이다.

위 경우에는 2000 | 1001 | 1001 로 시음하지 않는 경우가 가장 크다.

계단오르기 문제와 다른 부분도 이 부분이다.

 

for (int i = 3; i < n; i++) {
	wineDp[i] = Math.max(Math.max(wineDp[i-1],wineDp[i-3] + wine[i-1] + wine[i]), wineDp[i-2] + wine[i]);
}

index 3번 이상 부터도 시음을 하지 않는 것이 더 최대값을 가질 수 있다라는 것을 알려줘야한다.

순서대로

max(시음을 하지 않음 | 전전전것의 최대양 + 연속 두번의 양 | 전전 것의 최대양 + 현재의 양) 총 세가지 중의 최대값을 비교한다.

 

index : 3일때 2000 | 1002 | 2001

-> 현재 단계에서는 시음을 하는게 가장 큼

 

index : 4일때 2001 | 3001 | 3000

-> 전 단계에서 시음한것보다 전 단계를 시음하지 않고 현재양과 합한 양이 더 큼

 

index : 5일때 3001 | 4000 | 3001

 

결과는 

[1000, 2000, 2000, 2001, 3001, 4000] 과 같이 나올 것이고

그중 가장 큰 값 4000이 답이 된다.