[백준/Python] 2156번 - 포도주 시식

문제

2156번 - 포도주 시식

해결 과정

• d[i] 는 i번째 포도주까지 최대로 마신 포도주의 양이다. (0부터)
• d[0] : 1번째 포도주까지 최대로 마신 포도주의 양은 그 1잔을 마시는 것이다.
• d[1] : 2번째 포도주까지 최대로 마신 포도주의 양은 1번째 잔과 2번째 잔 모두 마시는 것이다.
• d[2] : 3번째 포도주까지 최대로 마신 포도주의 양은
  • 2번째 잔과 3번째 잔을 마시고 1번째 잔은 안 마시는 것 wine[1] + wine[2]
  • 1번째 잔과 3번째 잔을 마시고 2번째 잔은 안 마시는 것 wine[0] + wine[2]
  • 1번째 잔과 2번째 잔을 마시고 3번째 잔은 안 마시는 것 dp[1]
  • 세 가지의 경우 중에서 가장 최대 값을 넣기
• 점화식
  dp[i] = max(dp[i-1], wine[i] + dp[i-2], wine[i] + wine[i-1] + dp[i-3])
  • dp[i-1]: i번째 잔은 안마시고, i-1번째 잔까지의 최대로 마신 포도주 양
  • wine[i] + dp[i-2]: i번째 잔 마시고,i-2번째 잔까지의 최대로 마신 포도주의 양 (i-1번째는 안마심)
  • wine[i] + wine[i-1] + dp[i-3]: i번째 잔 마시고, i-1번째 잔 마시고, i-3번째 잔까지의 최대로 마신 포도주의 양

시행착오

• 점화식 세우는 건 너무 어렵다
• 이해하기 위해 노력
• 인덱스 에러

wine = [int(sys.stdin.readline()) for _ in range(n)]
dp = [0] * (n+1)

풀이

import sys
n = int(sys.stdin.readline())
wine = [0] * 10000
dp = [0] * 10000
for i in range(n):
  wine[i] = int(sys.stdin.readline())
  
dp[0] = wine[0]
dp[1] = wine[0] + wine[1]
dp[2] = max(dp[1], wine[0] + wine[2], wine[1] + wine[2])

for i in range(3,n):
  dp[i] = max(dp[i-1], wine[i] + dp[i-2], wine[i] + wine[i-1] + dp[i-3])

print(max(dp))