포도주 시식

문제 정보

• 백준 실버 1
• DP
• 문제 링크

풀이

dp[i]를 i번째 잔까지 고려했을 때 마실 수 있는 최대 포도주 양으로 정의한다.

연속으로 놓인 3잔을 모두 마실 수 없다는 규칙 때문에 다음과 같이 세 경우로 나뉘어 진다.

1. 직전 잔을 마시는 경우: dp[i - 3] + grape[i - 1] + grape[i]
2. 직전 잔을 마시지 않는 경우: dp[i - 2] + grape[i]
3. 현재 잔을 마시지 않는 경우: dp[i - 1]

세 경우 중 최대값이 dp[i]이다.

20260205 계단오르기 문제와 비슷하나, 이 문제는 마지막 잔을 반드시 마실 필요가 없다. 따라서, i번째 잔을 마시지 않더라도 i-1번째까지의 최대값(dp[i - 1])이 i번째까지의 최대값이 될 수 있다. 그렇기 때문에 ‘현재 잔을 마시지 않는 경우’를 추가로 고려해줘야 한다.

코드

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] grape = new int[n + 1];
        
        for (int i = 1; i <= n; i++)
            grape[i] = Integer.parseInt(br.readLine());
        
        if (n == 1)
            System.out.println(grape[1]);
        else if (n == 2)
            System.out.println(grape[1] + grape[2]);
        else {
            int[] dp = new int[n + 1];
            
            dp[1] = grape[1];
            dp[2] = grape[1] + grape[2];
        
            for (int i = 3; i <= n; i++) {
                dp[i] = Math.max(dp[i - 3] + grape[i - 1], dp[i - 2]) + grape[i];
                dp[i] = Math.max(dp[i], dp[i - 1]);
            }
        
            System.out.println(dp[n]);
        }
    }
}

관련 노트

• 20260205 계단오르기