99클럽 코테 스터디 12일차 TIL - 백준 2156번 : 포도주 시식

✅ 문제

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

 

✅ 분류

DP (다이나믹 프로그래밍)

✅ 공부한 내용

- 문제 요약

• 총 n개의 포도주 잔이 일렬로 있다.
• 한 번 마시면 모두 마셔야 하고, 마신 후에는 다음 잔으로 무조건 이동.
• 3잔 연속 마시는 건 불가능.
• 마실 수 있는 최대 포도주 양을 구해야 함.

- 풀이 로직

1. DP 배열 정의
   dp[i] = i번째 포도주까지 마실 수 있는 최대 양
   
2. 점화식 구성 (3가지 상황 존재)
   문제조건에서 연속으로 3잔을 마시면 안되기에
   wine[i-2], wine[i-1], wine[i]이 세 잔을 모두 마시는 경우는 안된다.
   
   i번째 포도주를 마시는 경우는 2가지 상황
   - (i - 2) 번째를 건너뛰고 (i - 1) 번째와 i번째를 연속으로 마신 경우:dp[i - 3] + wine[i - 1] + wine[i]
   - (i - 1) 번째를 건너뛰고 i번째만 마신 경우 : dp[i - 2] + wine[i] 
   
   i번째 포도주를 아예 마시지 않는 1가지 경우 : dp[i - 1] (그냥 이전 최댓값 유지)
   
   최종 점화식 
   - dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]));
3. 예시
   포도주 구성이 아래와 같은 예시
   wine = [0, 6, 10, 13, 9, 8, 1]
                     ↑ 1부터 시작 (인덱스 편의상)
   - dp[3] 을 구할 때는 :
      dp[2] = 6 + 10 = 16
      dp[1] + wine[3] = 6 + 13 = 19
      wine[2] + wine[3] + dp[0] =  10 + 13 + 0 = 23 → 최대값 23 선택

✅ 회고

문제 의도는 파악했지만, 한 번에 점화식을 도출해내는 게 아직 부족한 부분이다.

DP 문제를 더 풀어보고 좀 더 익숙해지는 게 중요한 것 같다.

 

🔑 풀이

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[] 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[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 - 1], Math.max(dp[i - 2] + wine[i], dp[i-3] + wine[i-1] + wine[i]));
            dp[i] = dp[i - 3] + wine[i - 1] + wine[i];
            dp[i] = Math.max(dp[i], dp[i - 2] + wine[i]);
            dp[i] = Math.max(dp[i], dp[i - 1]);
        }
        System.out.println(dp[n]);
    }
}