[JAVA] 백준 2156번 【포도주 시식】

포도주가 문제에 나와있는 예제처럼 있다고 가정해보자.

Dp[n]은 해당 n번째 까지, 포도주를 최대로 마신 량을 기록할 것이다.

Dp[1] 은 당연하게도 wine[1]이다. 1잔 밖에 없으니, 1잔을 마신게 최대값이 된다.

Dp[2] 역시 당연하게 wine[1]+wine[2] 가 된다. 연속으로 3잔을 마시는건 안되지만, 2잔을 마시는 건 허용이 된다.

그렇다면 Dp[3]은 어떻게 채울까

3가지 Case가 있을 수 있다.

Case.1

이미 1번째 잔과 2번째 잔을 마신 경우 3번째 잔은 마실 수 없고 Dp[3]은 더 마신 와인이 없으니,

변화없이 wine[1] +wine[2] = 16이 될 것이다.

Case.2

1번째 잔과 3번째 잔을 마실 경우, Dp[3]은 wine[1] + wine[3] = 19가 될 것이다.

Case.3

2번째 잔과 3번째 잔을 마실 경우, Dp[3]은 wine[3] + wine[2] =23 가 될것이다.

이 3가지 케이스 중, 가장 값이 큰 Case는 Case 3번으로, Dp[3]은 23으로 입력해야 할 것이다.

Dp[4]를 채우는 과정에서 패턴이 명확히 보일 것이다.

역시 3가지 Case 가 존재한다.

Case. 1

wine[2]와 wine[3]이 선택된 경우 wine[4]는 마실 수 없으므로, Dp[4]는 변화 없이, Dp[3]이 될 것이다.

즉 Dp[n] = Dp[n-1] 이 되는 경우의 수가 하나 생긴다.

Case. 2

wine[2]와 wine[4]를 선택한 경우, Dp[4] = Dp[2]+ wine[4]가 된다. Dp[2]인 이유는, 건너서 마셨든, 연달아 마셨든, wine[4]를 선택하는데 지장을 주지 않기 때문이다.

즉, Dp[n] = Dp[n-2] +wine[n] 이 되는 경우의 수가 하나 생긴다.

Case. 3

wine[3]과 wine[4]를 선택한 경우, Dp[4] = Dp[1] +wine[4]+wine[3]이 된다. 2번째 잔은 마시지 않았으니, 2번째 잔이 포함되지 않은 Dp[1]까지의 값을 더해준다.

즉, Dp[n] = Dp[n-3] + wine[n] + wine[n-1] 이 되는 경우의 수가 생긴다.

즉, Dp[n]은 Dp[n-1] 와 Dp[n-2] +wine[n] 와 Dp[n-3] + wine[n] + wine[n-1] 중 최댓값을 선택하면 된다.

사실, Dp[3]을 채울때에도 위 식을 적용할 수 있었다.

위 점화식을 바탕으로 코드를 작성하면 된다!

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		
		long [] wine = new long[n+2];
		long [] Dp = new long[n+2]; 
		// wine 배열과 Dp 배열 생성, 초기값을 2까지 채워주기 위해
		
		
		for(int i=1;i<=n;i++) {
			wine[i]=scanner.nextInt(); //wine 배열 데이터 채우기
		}
		
		Dp[1]=wine[1];
		Dp[2]=wine[1] + wine[2]; // 잔 갯수 2 이상일때 초기값
		
		for(int i = 3;i<=n;i++) {
			Dp[i]=Math.max(Dp[i-1], Dp[i-2]+wine[i]);
			
			Dp[i]=Math.max(Dp[i], Dp[i-3]+wine[i]+wine[i-1]);
			//3가지 Case 중 최댓값을 저장
		}
		
		System.out.println(Dp[n]);
	}
}

티스토리툴바