[파이썬][백준] 2156번 포도주 시식

백준 온라인저지 2156번 포도주 시식

문제풀러 바로가기👇👇👇👇👇👇

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

 

 

문제풀이

---

다이나믹 프로그래밍을 이용해 문제를 풀 수 있다. 연속으로 3잔을 마실 수 없는 조건을 만족시켜야하고, 최대한 많은 포도주를 마셔야하기 때문에 점화식을 잘 세우고, max 메소드를 이용해야한다.

 

wine 맨 앞에 0인 더미 값을 넣어줘 dp와 인덱스를 맞춰줬다. 아래 코드를 통해 점화식을 도출해보자.

dp[1]와 dp[2]은 점화식이 따로 필요없이 확정되는 값이다. dp[3]부터 차례로 포도주의 최대값을 구하는 식을 만들면 공통점이 보일 것이고, 그것을 통해 점화식을 유추해낼 수 있다.

 

 

 

wine = [0, 6, 10, 13, 9, 8, 1]
dp = [0] * (n+1)
dp[1] = wine[1]

# n의 범위가 1이상이므로 예외 분기를 넣어야한다.
if n > 1:
    dp[2] = wine[1] + wine[2]

# 점화식 도출
dp[3] = max(dp[1] + wine[3], dp[2], dp[0]+wine[2]+wine[3])
dp[4] = max(dp[2] + wine[4], dp[3], dp[1]+wine[3]+wine[4])

# 점화식은 dp[i] = max(dp[i-2]+wine[i], dp[i-1], dp[i-3]+wine[i-1]+wine[i]) 이다.

이제 점화식을 바탕으로 코드를 짜면 된다.

 

 

코드

---

n = int(input())
wine = [0]
for i in range(n):
    wine.append(int(input()))

dp = [0] * (n+1)
dp[1] = wine[1]
if n > 1:
    dp[2] = wine[1] + wine[2]

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

print(dp[n])