[백준/BOJ] 백준 코딩 알고리즘 2156번 포도주 시식 Python (다이나믹 프로그래밍)

 

나의 풀이

import sys
input = sys.stdin.readline

N = int(input())
wines, dp = [], [0] * N
for _ in range(N):
  wines.append(int(input()))

for i in range(N):
  if i == 0:
    dp[i] = wines[i]
  elif i == 1:
    dp[i] = dp[i - 1] + wines[i]
  elif i == 2:
    dp[i] = max(dp[i - 1], max(wines[i - 1] + wines[i], dp[i - 2] + wines[i]))
  else:
    dp[i] = max(dp[i - 1], max(dp[i - 3] + wines[i - 1] + wines[i], dp[i - 2] + wines[i]))
      
print(dp[-1])

 

본 문제에서는 점화식과 메모이제이션을 통해

이전에 계산한 값을 다시 계산하지 않고 불러옴으로써 풀이가 가능하다

 

우선 와인이 3개 이하인 경우는 따로 if문을 통해 처리해준다

 

그리고 와인이 4개 이상인 경우는 다음과 같이 처리한다 (3잔 이상 연속으로 마실 수 없는 조건에 유의한다!)

 

우선 현재 보고 있는 i번째 와인에 대해서 고려했을 때, 다음과 같이 3가지 경우로 나눌 수 있다

i번째 와인을 마시는 경우 - a) 전전전 와인까지 마시기 + 전 와인 마시기 + 현재 와인 마시기 (전전 와인을 안마신다)

i번째 와인을 마시는 경우 - b) 전전 와인까지 마시기 + 현재 와인 마시기 (전 와인을 안마신다)

i번째 와인을 마시지 않는 경우) 전 와인까지 마시기 (현재 와인을 안마신다)

 

위 세 가지 경우에 대한 최대값을 dp 배열에 저장하고

이를 불러와 사용하며 업데이트 해나가면

dp배열의 가장 마지막 칸에는 최대값이 저장되어있기 때문에 문제를 풀 수 있다

 

내가 생각하기에 이번 문제를 풀 때 주의해야할 점은 다음과 같다.

- 점화식을 어떻게 세울지 잘 정의하는 것

- 정의한 점화식을 구현할 때, wines 배열과 dp 배열을 혼동하지 않는 것!