[Algorithm] 백준 2156 - 포도주 시식 in Python(파이썬)

💡 백준 2193:

최대로 마실 수 있는 포도주의 양 DP 탐색

🌱 코드 in Python

알고리즘: Dynamic Programing

import sys

input = sys.stdin.readline
n = int(input())
w = [int(input()) for _ in range(n)]
dp = [0] * n

dp[0] = w[0]
if n > 1:
	dp[1] = w[0] + w[1]
if n > 2:
	dp[2] = max(dp[1], max(w[0], w[1]) + w[2]) # 현재 잔을 마시지 않거나, 마시는 경우 
for i in range(3, n):
	dp[i] = max(dp[i - 1], w[i] + w[i - 1] + dp[i - 3], w[i] + dp[i - 2]) # 현재 잔을 마시지 않거나, 내 전 잔과 연달아 마시고 2개 전것을 건너뛰고 마시거나, 내 전 잔과 연달아 마시지 않는 경우
print(max(dp))

DP는 아직도 헷갈린다 아직도 헷갈려 ㅠㅠ!

이번 문제에서 내가 빠졌던 함정은
문제 배열이 6, 1, 1, 0, 0, 1, 1과 같이 주어졌을 때 무조건 한 칸만 건너서 마신다고 생각해서
답이 3이 나왔었는데, 실제 답은 4가 나와야 한다
중간에 2칸을 건너뛰고 마실 수 있기 때문이다

그래서 이번에는 나를 마시지 않는 경우를 포함하여 max 비교를 해주었어야 했다
하.. 어렵고도 먼 디피~!

🧠 기억하자

1. 3잔을 연달아 마실 수 있다는 것이 꼭 2잔에 1잔만 걸러 마시라는 소리는 아니다!

백준 2156 바로가기