백준 포도주 시식 코드 및 해설 (파이썬)
2021. 11. 9. 14:50ㆍalgorithm
반응형
https://www.acmicpc.net/problem/2156
다이나믹 프로그래밍 문제다. 연속적으로 3잔의 포도주를 먹을 수 없다는 제한이 있다.
i번째 포도주에 해당하는 dp값은 i번째 포도주를 마시는 경우와 마시지 않는 경우로 나눌 수 있는데
(1) i번째 포도주를 마시는 경우
(1.1) i-1번째와 i번째 포도주를 마시는 경우: i-2번째는 먹지 못하니까 dp[i-3] + wine[i-1] + wine[i]
(1.2) i-1번째 포도주는 마시지 않고 i번째 포도주만 마시는 경우: i-2번째도 마실 수 있으니 dp[i-2] + wine[i]
(2) i번째 포도주를 마시지 않는 경우
i-1번째까지 최댓값을 구하면 되니까 dp[i-1]
이 모든 경우 중 최댓값을 취하면 된다
import sys
n = int(sys.stdin.readline())
wine = []
for _ in range(n):
wine.append(int(sys.stdin.readline()))
if n < 3:
print(sum(wine))
else:
dp = [0] * n
dp[0] = wine[0]
dp[1] = dp[0] + wine[1]
dp[2] = max(wine[0] + wine[2], wine[1] + wine[2], dp[1])
if n > 3:
for i in range(3, n):
# i번째 포도주를 마신 경우
# i-1, i번째 포도주를 마신 경우: dp[i - 3] + wine[i - 1] + wine[i]
# i-1번째 포도주는 마시지 않고 i번째 포도주만 마신 경우: dp[i - 2] + wine[i]
# i번째 포도주를 마시지 않은 경우: dp[i-1]
dp[i] = max(dp[i - 3] + wine[i - 1] + wine[i], dp[i - 2] + wine[i], dp[i - 1])
print(dp[-1])
반응형
'algorithm' 카테고리의 다른 글
백준 계단 오르기 코드 및 해설 (파이썬) (0) | 2021.11.11 |
---|---|
백준 컨베이어 벨트 위의 로봇 코드 및 해설 (파이썬) (0) | 2021.11.08 |
백준 미세먼지 안녕! 코드 및 해설 (파이썬) (0) | 2021.11.03 |
백준 색종이 코드 및 해설 (파이썬) (0) | 2021.11.03 |
프로그래머스 모음사전 코드 및 해설 (파이썬) (0) | 2021.11.03 |