(Python/파이썬) 백준 2156번 - 포도주 시식

문제출처: https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

1. 코드

n = int(input())
wine = []
 
for i in range(n):
    wine.append(int(input()))
 
#wine 0부터 시작이니까 wine[0]=1잔
dp = [0]*n
dp[0] = wine[0]
dp[1]=wine[0]+wine[1]
dp[2]=max(wine[2]+wine[0],wine[2]+wine[1],dp[1])
 
 
for i in range(3, n):
    #1. 이전 와인, 현재와인 마시고, 전전 와인 안마심 : wine[i-1]+wine[i]+dp[i-3]
    #2. 현재와인 마시고,이전 와인 안마심 : wine[i]+dp[i-2]
    #3. 현재와인 안마심
    dp[i] = max(wine[i-1]+wine[i]+dp[i-3], wine[i]+dp[i-2], dp[i-1])
 
print(dp[n-1])

2. 해결과정

wine이라는 빈 리스트에 와인 양을 넣어준다.

dp 리스트를 설정해주고,

dp[0] = wine[0]

dp[1]=wine[0]+wine[1] 을 미리 작성해준다.

dp[2]의 경우 연속해서 3잔을 마시면 안되기 때문에 마실 것 중에 양이 많은 것 2개를 골라줘야 하므로 max(wine[2]+wine[0],wine[2]+wine[1],dp[1]) 를 도출해 낼 수 있다.

이제 4잔부터 n까지를 생각해주면 

#1. 이전 와인, 현재와인 마시고, 전전 와인 안마심 : wine[i-1]+wine[i]+dp[i-3]

#2. 현재와인 마시고,이전 와인 안마심 : wine[i]+dp[i-2]

#3. 현재와인 안마심

의 규칙을 찾을 수 있고, 3가지 케이스 중에서 가장 큰 값을 출력해주면 된다.

 

3. 느낀점

규칙 찾기 어려웠다...dp는 진짜로 연습 많이 해야할 것 같다. ㅜ