링크

2156 포도주 시식

문제

풀이

이 문제 푸는데 되게 오래 걸렸다. 비슷한 문제로 계단오르기라는 문제가 있다.

이 문제는 DP로 풀어야 하고 3개 연속으로 포도주를 마시면 안된다.

(맨 밑의 그림을 보자)
1번 인덱스에서 4번 인덱스로 도착하는 경우의 수가 2개가 있다.(1칸 + 1칸과 같은 경우는 3잔 연속을 마시는 경우를 제외 못하기 때문에 3일 연속으로 안마시게 하는 방법은 1 + 2 거나 2 + 1이다.)

1. 1번처럼 1번 인덱스에서 2단점프 + 1단점프
2. 2번처럼 1번 인덱스에서 1단점프 + 2단점프
3. 3번은 2단점프 2번인데 잘 생각해보면 2번의 경우의 수와 같다. 왜냐하면 dp를 통해서 최대값을 갱신하는데 2번과 3번 모두 2번 인덱스를 경유하기 때문에 2번 인덱스에서 4번 인덱스로 2단점프하면 값이 똑같기 때문이다.

그리고 현재 dp를 저장할때 전의 값도 비교해야 한다. 왜냐하면 최대로 마시는 경우의 수이기 때문에 dp[i]보다 dp[i-1]의 크기가 크면 dp[i-1]로 값을 내야하기 때문이다.

그러면 2번을 보면 1단 점프 + 2단 점프를 하나 2단점프나 똑같다. 왜냐하면 dp[i-1]로 최대 이득인 경우를 계속 저장하기 때문에 1단점프 + 2단점프나 2단점프나 같다 그래서 2단점프로 정리가 된다.

점화식을 세워보면
dp[i] = dp[i-1], dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]이다.

마지막 점화식인 dp[i-3] + arr[i-1] + arr[i]가 왜 나왔는지 자세히 보자면 만약 dp[i-3] + dp[i-1] + arr[i]이 된다고 하면
dp[i-1] + arr[i]와 똑같은 식이 되고 그럼 1단점프니까 3번 연속 먹는 로직이 되기 때문이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		 
		int[] arr = new int[N + 1];
		int[] dp = new int[N + 1];
 
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		if(N == 1) System.out.println(arr[1]);
		else if(N == 2) System.out.println(arr[1] + arr[2]);
		else {			
			dp[0] = 0;
			dp[1] = arr[1];
			dp[2] = arr[1] + arr[2];
			
			for(int i=3;i<dp.length;i++) {
//			System.out.println(i);
//			System.out.println("dp[i-3] + arr[i-1] + arr[i] = " + (dp[i-3] + arr[i-1] + arr[i]));
//			System.out.println("dp[i-2] + arr[i] = " + (dp[i-2] + arr[i]));
//			System.out.println("------------------");
				
				dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]));
			}
			
//		System.out.println(Arrays.toString(arr));
//		System.out.println(Arrays.toString(dp));
			System.out.println(dp[N]);
		}
	}
	
}