PS/백준

2156번 - 포도주 시식

ForteQook 2022. 10. 22. 12:23

풀이

2156번: 포도주 시식 (acmicpc.net)

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

문제

dp[i]를 i 번째 와인을 골랐을 때 마실 수 있는 와인 양의 최대값으로 한다.3 잔 연속으로 마실 수 없다는 점에 착안하여 점화식을 세우되, i-1 번째 와인을 마시면 i-4 번째 와인을 마시는 경우와 i-3 번째 와인을 마시는 경우 두가지가 존재한다는 점을 주의하자.

N = int(input())
wine = [0]*10001
for i in range(1,N+1):
    wine[i] = int(input())

dp = [0]*10001
dp[1] = wine[1]
dp[2] = wine[1]+wine[2]
dp[3] = max(wine[1],wine[2]) + wine[3]
for i in range(4,N+1):
    dp[i] = max(wine[i-1]+dp[i-4],wine[i-1]+dp[i-3],dp[i-2]) + wine[i]

print(max(dp[N],dp[N-1]))

'PS > 백준' 카테고리의 다른 글

11054번 - 가장 긴 바이토닉 부분 수열  (0) 2022.11.04
11053번 - 가장 긴 증가하는 부분 수열  (0) 2022.11.04
10844번 - 쉬운 계단 수  (1) 2022.10.22
1463번 - 1로 만들기  (0) 2022.10.22
2579번 - 계단 오르기  (0) 2022.10.21