2156

날짜 : 2022. 11. 19

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
dp = [0] * n
wine = list()

for _ in range(n): 
    wine.append(int(sys.stdin.readline().rstrip()))

if n == 1: print(wine[0])
elif n == 2:print(wine[0]+wine[1])
else: 
    dp[0] = wine[0]
    dp[1] = wine[0] + wine[1]
    dp[2] = max(wine[0]+wine[2], wine[1]+wine[2], dp[1])

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

 

 

풀이

- 각각 입력한 포도주의 개수가 1, 2인 경우에는 단순 비교만으로 출력 가능

- 그 이상인 경우 해당 포도주를 넣어서 비교한 경우를 비교군에 넣어 비교한다.

- 연속으로 3잔 이상을 마실 수는 없기 때문에 연속으로 2잔을 마시고 건너 뛴다음 바로 전 포도주를 마신 경우와

  앞 앞 포도주까지 마신 후 건너뛴 경우를 비교한다.

- 그리고 해당 차례의 포도주를 넣어서 마신 총량과 바로 앞 포도주 차례까지의 경우까지 비교해서 큰 수를 해당 dp 리스트에 저장한 후 dp 리스트의 최댓값을 출력한다.

 

 

알게된 점

- 앞서 풀어보았던 문제(https://www.acmicpc.net/problem/2579)와 비슷해서 같은 방향으로 풀어보려 했지만 마지막에 dp[n-1]이라는 비교군을 생각하지 못해 꽤 많이 생각하고 풀이를 찾아본 것 같다.

 

 

참고 사이트

-