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

오늘의 학습 키워드

• 동적 계획법, DP
• 부분합
• 최대값 갱신
• 상태 저장

---

공부한 내용 정리

이번 문제는 연속으로 3잔의 포도주를 마실 수 없다는 조건 하에
가장 많은 양의 포도주를 마시는 경우를 찾는 문제였습니다.

핵심은 지금 잔을 마시느냐 마시지 않느냐를 기준으로
3가지 경우를 비교하는 방식으로 dp[i]를 정의한 것입니다.

dp[i] = max(
    dp[i - 1],                               // 현재 잔을 마시지 않는 경우
    dp[i - 2] + glass[i],                    // 현재 잔만 마시는 경우
    dp[i - 3] + glass[i - 1] + glass[i]      // 현재 잔과 이전 잔을 마시는 경우
);

이렇게 함으로써, 세 잔 연속으로 마시는 경우를 방지할 수 있었습니다.
포도주 양은 배열 glass, 결과를 저장할 배열은 dp로 선언하여 1-based index를 사용해 혼란을 줄였습니다.

---

소스코드

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[] glass = new int[n + 1]; // 포도주 양, 1-based
        for (int i = 1; i <= n; i++) {
            glass[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[n + 1];

        // ---- 초기값 세팅
        dp[1] = glass[1];
        if (n >= 2) dp[2] = glass[1] + glass[2];

        // ---- DP 점화식
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(
                dp[i - 1],
                Math.max(dp[i - 2] + glass[i], dp[i - 3] + glass[i - 1] + glass[i])
            );
        }

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

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 단순히 많이 마신 잔을 고르면 되지 않을까 싶었지만,
"연속 3잔 마시면 안 된다"는 조건 때문에 단순 누적합으로는 해결이 불가능했습니다.
이로 인해 이전 상태를 고려하면서 결정하는 방식, 즉 DP가 필요하다고 판단했습니다.

 

• 어떻게 해결했는지

점화식을 세우고, 조건에 따라 세 가지 경우 중 최댓값을 선택해 dp[i]를 구성했습니다.
특히 dp[i - 3] + glass[i - 1] + glass[i] 부분이 핵심이었는데,
이것이 연속 3잔을 피하면서도 2잔을 연속으로 마시는 경우를 잘 반영하고 있었습니다.

 

• 무엇을 새롭게 알았는지

DP 문제는 초기값 세팅이 매우 중요하다는 점을 다시 느꼈습니다.
또한, 이전 3개의 상태만 고려하면 되기 때문에 최적화된 메모리 사용이나 Bottom-Up 방식이 더 효과적일 수 있다는 점도 함께 떠올렸습니다.

 

 

 

• 내일 학습할 것은 무엇인지

내일은 DP 응용 문제인 계단 오르기 또는 RGB 거리 같은 문제들을 풀어보며
다양한 상태 정의와 점화식 구성을 연습할 계획입니다.

---