[백준] 2156번: 포도주 시식(DP)

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

2156번: 포도주 시식

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] arr = new int[n];
		int[] dp = new int[n];
		for(int i=0; i<n; i++)
			arr[i] = scan.nextInt();
		
		// 잔의 개수가 1일때 -> 그잔 마시면 됨
		if(n>=1) 
			dp[0] = arr[0];
		// 잔의 개수가 2일때 -> 첫잔 + 두번째잔 마시면 됨
		if(n>=2) 
			dp[1] = arr[0] + arr[1];
		// 잔의 개수가 3일때 -> (첫잔+두번째잔) , (첫잔+세번째잔) , (두번째잔+세번째잔) 중 큰 값 비교 
		if(n>=3)
			dp[2] = Math.max(dp[1], Math.max(arr[0]+arr[2], arr[1]+arr[2]));
		
		for(int i=3; i<n; i++) {
			dp[i] = Math.max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i]);
			dp[i] = Math.max(dp[i], dp[i-1]);
		}
		
		System.out.println(dp[n-1]);
		scan.close();
	}

}

풀이

DP(동적계획법) 문제는 경우의 수를 찾고, 점화식을 세우는것이 우선인 것 같다.

위 문제에서 중요한 조건은 2번째인 다음 조건이다.

* 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

 

위 문제에서 현재 먹는 포도주의 합을 최대로 만들 경우를 생각해보면

 1) 현재 포도주를 마시고, 이전 포도주를 마신 경우

 2) 현재 포도주를 마시고, 이전 포도주를 마시지 않은 경우

 3) 현재 포도주를 마시지 않은 경우

로 총 세개의 경우로 나눌 수 있다.

 

 

dp[i] : i번째까지 마신 포도주 중 최대로 마실수 있는 양

arr[i] : i번째에 마시는 포도주의 양

 

 

위와 같이 마지막잔, 마지막 앞 잔을 마셨을 경우, 마실수 있는 포도주의 최대 양은

dp[i] = dp[i-3] + arr[i-1] + arr[i] 이다.

 

 

두 번째로는, 마지막잔을 마시고, 그 앞잔을 마시지 않았을 경우를 보자.

위와 같을때 마실수 있는 포도주의 최대 양은

dp[i] = dp[i-2] + arr[i] 이다.

 

 

세 번째로 마지막잔을 마시지 않았을 경우에는 그 앞 두잔을 마시게 된다.

따라서 위와 같을때 마실수 있는 포도주의 최대 양은

dp[i] = dp[i-1] 이다.

 

위에서 구한 3개의 점화식 중 최댓값을 찾으면 된다.

 

dp[i-3] + arr[i-1] + arr[i] , dp[i-2] + arr[i] , dp[i-1]