[BOJ 2156] 포도주 시식 (Java)

문제

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

2156번: 포도주 시식

포도주 시식

풀이

• arr[i]= i번째 잔의 포도주양
• dp[i] = i번째 잔까지 있을 때 마실 수 있는 최대 포도주 양

세 가지 경우로 나누어 볼 수있다. 

1. i번째 잔을 마시지 않았을 경우

dp[i] = 이전 잔까지 있을 때의 마실 수 있는 최대 포도주 양

dp[i] = dp[i-1] 

 

2. i번째 잔을 한 번 연속으로 마실 경우 

i-1번째 잔을 건너 뛰어야 한다. 

dp[i] = dp[i-2] + arr[i]

 

3. i번째 잔을 두 번 연속으로 마실 경우 

i-3번째 까지의 최대 포도주 양에다가 i-2번째 포도주잔은 건너뛰고, i-1, i 잔의 포도주 양을 더하면 된다. 

dp[i] = dp[i-3] + arr[i-1] + arr[i]

 

dp[i]는 위에서 계산한 세 개의 값중 최대값이 된다. 

i가 1, 2일때만 예외처리해주고, 나머지는 위 점화식으로 값을 저장하다 보면 dp의 마지막 index에 답이 담긴다.

index	1	2	3	4	5	6
arr	6	10	13	9	8	1
i번째 잔을 안 마신다	0	6	dp[2] = 16	dp[3] = 23	dp[4] = 28	dp[5] = 33
i번째 잔을 한 번 연속으로 마신다	6	10	dp[1]+arr[3] = 6+13 = 21	dp[2]+arr[4] = 16+9 = 25	dp[3]+arr[5] = 23+8 = 31	dp[4]+arr[6] = 28+1 = 29
i번째 잔을 두 번 연속으로 마신다.	6	16	dp[0]+arr[2]+arr[3] = 0+10+13 = 23	dp[1]+arr[3]+arr[4] = 6+13+9 = 28	dp[2]+arr[4]+arr[5] = 16+9+8 =33	dp[3]+arr[5]+arr[6] =23+8+1 =32

 

소스코드

package dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ2156 {

    public static void main(String[] args) throws Throwable{
        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]; //dp[i] = i잔 까지 포도주가 있을 때, 지금까지 마신 포도주 양의 최대값
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = arr[1];
        if(N > 1) dp[2] = arr[1] + arr[2];
        for(int i = 3; i <= N; i++){
            // 1. i잔을 안마신다.
            dp[i] = dp[i-1];

            // 2. i잔을 한 번 연속으로 마신다.
            dp[i] = Math.max(dp[i], dp[i-2] + arr[i]);

            // 3. i잔을 두 번 연속으로 마신다.
            dp[i] = Math.max(dp[i], dp[i-3] + arr[i] + arr[i-1]);

        }
        System.out.println(dp[N]);
    }
}