[BOJ] 2156 포도주 시식 - python(파이썬)

 

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

2156번: 포도주 시식

---

연속으로 세잔은 먹을 수 없다고 한다.

 

그렇다면 경우의 수는

1. 이전 두 잔을 먹고 이번 잔을 먹지 않는 경우

2. 두번째 전 잔과 이번 잔을 먹는 경우 

3. 이전 잔과 이번 잔을 먹는 경우

세 가지가 될 수 있다. 

 

해당 포도주 까지의 최댓값을 저장할 dp 배열, 포도주의 양을 담은 data를 이용해 경우의 수를 다시 작성하면

1. dp[i-1]

2. dp[i-2] + data[i]

3. data[i] + data[i-1] + dp[i-3]

중 가장 큰 값을 dp에 넣어주면 된다.

 

이때 dp의 0,1,2번 인덱스는

dp[0] = data[0] # 0번 포도주만 마심
dp[1] = data[0] + data[1] # 0,1 번 포도주를 모두 마심
dp[2] = max(data[0] + data[2], data[1] + data[2], dp[1]) # 0,2 1,2 1,2 마신것중 최댓값

각각 이렇게 값을 넣어둔 뒤 반복문을 돌려 결과를 도출하면 된당

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
data = [0] * 10000
for i in range(n):
    data[i] = int(input())

dp = [0] * 10000

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

print(max(dp))

---

https://github.com/wwan13

wwan13 - Overview