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

www.acmicpc.net/problem/2156

2156번: 포도주 시식

2가지 규칙이 있다.

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

연속으로 최대 2잔만 마실 수 있는 것이 관건이다.

 

3번째 잔부터 경우의 수 3가지로 나누어서 계산한다.

 

1. 앞의 두잔을 마셔서 현재 잔을 못마시는 경우 ( O O X )

2. 바로 앞의 잔만 마시고 현재 잔도 마시는 경우 ( X O O )

3. 앞앞의 잔만 마시고 현재 잔도 마시는 경우 ( O X O )

 

여기서 2번의 경우에 4번째 잔부터는 1 .... i-3 / i-2 / i-1 / i 이렇게 된다. i-2 잔을마시지 않고 i-3을 마셨을 경우에 가장 큰값을 더해주는 처리가 필요하다... 나는 이부분을 해결 못해서 해설을 봤다..

limkydev.tistory.com/112

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

	public static int[] wine;
	public static int[] dp;
	public static void main(String[] args)  {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		wine = new int[N+1];
		dp = new int[N+1];
		for (int t = 1; t <= N; t++) {
			wine[t] = sc.nextInt();
		}
		
		dp[1] = wine[1];
        if(N>1)
		    dp[2] = wine[1]+wine[2];
		
		for (int i = 3; i <= N; i++) {
			//경우의 수
			//1. 앞의 두잔을 마신상태여서 안먹을 경우
			//2. 바로 앞(i-1)꺼만 마신상태에서 지금의 잔도 먹을 경우(+ 4번째 잔부터라면 i-3일때 가장많이 마실 수 있는 양도 더해줌)
			//3. i-2꺼만 마시고 i-1는 안마신상태에서 먹을 경우
			dp[i] = Math.max(dp[i-1], 
					Math.max(wine[i-1]+wine[i]+dp[i-3], 
							dp[i-2]+wine[i]));
			
		}
		
		System.out.println(dp[N]);
		
	}

}