오늘은 백준 2156번 '포도주 시식' 문제를 풀면서 다이나믹 프로그래밍(DP)의 핵심을 다시 한번 깊이 깨닫는 시간을 가졌습니다. 처음에는 문제의 제약 조건을 그대로 옮기려 복잡한 모델링을 시도했지만, '시간'이라는 관점으로 문제를 재해석하는 순간 모든 것이 명확해졌습니다.

포도주 시식 DP: '시간'으로 문제를 바라보는 순간

학습 주제

오늘 공부한 주제: 백준 2156번 포도주 시식 문제 DP 풀이
대화 제목: 포도주 시식 DP
학습 날짜: 2026년 2월 12일

질문과 탐구

문제는 n개의 포도주를 마시되, 연속으로 3잔 이상 마시면 안 된다는 제약 조건 하에 최대로 마실 수 있는 포도주의 양을 찾는 것이었습니다. 처음에는 포도주들을 평면으로 보고 각 포도주를 노드로 간주, 선택 가능한 관계를 간선으로 연결하는 그래프 방식으로 접근했습니다. 과거 선택 기록을 map에 저장하고, 연속 여부를 판정하는 별도 함수를 만들어 이를 통해 접근을 차단하려 했습니다.

주요 질문들

포도주들을 어떻게 연결하고, 어떤 상태를 저장해야 연속 3잔 제약을 만족시킬 수 있을까?
map을 사용하여 과거 선택을 모두 기억해야 할까?
2차원 DP 배열(dp[몇번째 선택][포도주 인덱스][금지 여부]) 같은 복잡한 구조가 필요할까?

핵심 학습 내용

AI와의 대화를 통해 제가 처음에 문제를 **'공간'**으로 모델링했다는 것을 알게 되었습니다. 즉, 포도주들을 공간상의 위치로 보고 그 사이를 이동하는 문제로 생각했던 것이죠. 하지만 이 문제는 **'시간'**의 흐름에 따라 문제를 바라봐야 했습니다.

중요한 포인트 정리

시간축 DP: 포도주 배열은 공간이 아닌 **'시간'**입니다. 1번째 포도주는 1번째 시점, 2번째는 2번째 시점... 이렇게 시간 순서대로 진행하며, 뒤로 돌아갈 수 없습니다.
DP 정의: dp[i]는 1번째부터 i번째 포도주까지 고려했을 때 얻을 수 있는 최대 양으로 정의됩니다. 이는 i 시점까지의 최적해가 i-1, i-2, i-3 시점의 최적해로부터 구성된다는 'Prefix 최적화' 개념을 따릅니다.
3가지 경우의 수: i번째 포도주를 마시는 경우, i-1번째를 마시는 경우, i-2번째를 마시는 경우로 나누면 연속 3잔 금지라는 제약을 만족시킬 수 있습니다. AI가 설명한 '안 마신 시점'을 기준으로 나누는 것이 핵심입니다.
- Case 1: i번째를 안 마신다.
  - 패턴: ... - _
  - 최대 양: dp[i-1]
- Case 2: i-1번째를 안 마신다 (즉, i번째와 i-1번째를 마신다).
  - 패턴: ... - _ -
  - 최대 양: dp[i-2] + wine[i]
- Case 3: i-2번째를 안 마신다 (즉, i번째와 i-1번째, i-2번째를 마신다).
  - 패턴: ... - _ - -
  - 최대 양: dp[i-3] + wine[i-1] + wine[i]

전이식: 위의 3가지 경우를 종합하면 다음과 같은 DP 점화식이 도출됩니다.

dp[i] = max(
    dp[i-1],                       // Case 1: i번째 안 마심
    dp[i-2] + wine[i],             // Case 2: i-1에서 끊김
    dp[i-3] + wine[i-1] + wine[i]  // Case 3: i-2에서 끊김
)

이해한 내용

새로 알게 된 것: DP 문제에서 제약을 '탐색'이나 '검사'의 영역으로 생각하지 않고, DP 점화식 자체에 녹여내는 것이 중요하다는 것을 배웠습니다. 특히, '연속'이라는 제약은 '끊기는 지점' 또는 '안 마신 시점'을 기준으로 경우를 나누는 것이 논리적으로 명확하고 간결하다는 인사이트를 얻었습니다.
이전에 몰랐던 것과 연결: 저는 처음에 제약 조건을 만족시키기 위해 '과거를 모두 기억'하고 '별도의 판정 함수'를 사용하려 했습니다. 이는 마치 복잡한 게임의 모든 상태를 관리하려는 것과 같았습니다. 하지만 DP는 과거의 '최적해' 만을 요약해서 다음 상태를 계산하는 것이 핵심이라는 것을 깨달았습니다.
개념 정리: DP는 '시간'의 흐름에 따라 문제를 바라보고, 각 시점에서의 '최적해'를 바탕으로 다음 시점의 최적해를 도출하는 알고리즘입니다. 제약 조건은 DP 점화식 자체에 자연스럽게 녹여내야 하며, 불필요한 상태를 관리하려 하지 않아야 합니다.

실전 적용

이 지식을 바탕으로 실제 코딩 테스트 문제 풀이에 적용할 수 있을 것입니다. 특히, 유사한 '연속' 제약 조건이 있는 문제들을 만났을 때, '시간'의 흐름과 '끊기는 지점'을 기준으로 DP를 설계하는 연습을 해보겠습니다.

실습 계획

연속 K개 제한이 있는 유사 DP 문제들을 찾아 풀어보기.
'시간'과 '공간' 관점으로 문제를 구분하여 DP 접근 방식 연습하기.

응용 아이디어

주식 가격 예측에서 '연속 하락/상승' 제약을 고려한 DP 모델링.
회의실 예약 시스템에서 '연속 회의' 제약을 고려한 최적 예약 알고리즘 설계.

추가 학습 계획

더 깊이 공부하고 싶은 부분: DP에서 '상태 공간을 줄이는' 기법들에 대해 더 학습하고 싶습니다. 이번 문제에서는 '마지막으로 안 마신 시점'으로 상태가 압축되었는데, 다른 문제에서는 어떤 방식으로 상태를 줄일 수 있는지 알고 싶습니다.
관련 자료 찾기: 'DP의 일반적인 패턴'이나 '제약 조건을 DP에 녹이는 방법'에 대한 자료를 찾아보겠습니다.
다음 학습 주제: 이번에 DP의 강력함을 다시 한번 느꼈기에, DP를 활용한 다양한 문제들을 계속 풀어보며 실력을 키우고 싶습니다.

참고 자료

AI와의 대화에서 언급된 백준 2156번 포도주 시식 문제의 핵심 원리.
DP 점화식: dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])