2156 - 포도주 시식

문제: boj.kr/2156
날짜: 08/30 (금)
성공여부: X

 

n = 1일 때

 

n = 2일 때

 

n = 3일 때

 

n = 4일 때

 

n = 5일 때

 

n = 1 or 2일 때는 무조건 1을 먹고 1, 2를 먹는게 최대값이다.

 

그럼 진짜 로직의 시작은 n = 3일 때부터이다. n이 3일 때부터 보면 3가지의 경우의 수로 나뉜다.

 

n을 먹지않고 이전(n-1)까지 먹은 것을 선택하거나, n-2까지의 먹은 것을 선택하고 n을 먹거나, n-3까지의 먹은 것을 선택하고 n-1, n의 와인을 먹는 것이다. 이를 식으로 나타내면

 

Math.max(dp[n-1], dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n])

 

문제가 계단 오르기 문제와 유사해서 dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n] 식으로만 생각했는데, 꼭 마지막 와인을 먹지 않아도 최댓값 일 수 있다. 연속 3잔을 먹지 못한다는 조건 때문에 마지막 와인을 먹는다는 선택이 꼭 그 상황에서 최댓값을 보장해주지 않는다.

 

코드

import java.io.*;

public class Main {
    // 시간제한 2초, 메모리제한 128MB

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] wine = new int[n+1];
        for (int i = 1; i <= n; i++) wine[i] = Integer.parseInt(br.readLine());

        int[] dp = new int[n+1]; dp[0] = 0; dp[1] = wine[1];
        if (n >= 2) dp[2] = wine[1] + wine[2];

        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]);
            dp[i] = Math.max(dp[i], dp[i-1]);
        }

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