[Baekjoon] 백준 2156 포도주 시식(실버 1) - Python

문제설명

예제

문제를 살펴보면 이전에 풀이하였던 2579 계단오르기 문제와 굉장히 유사하다

처음에는 2칸이라는 조건이 없고, 마지막 잔을 꼭 먹어야한다는 조건이 없다 라는 두가지가 다른줄 알았으나,

곰곰히 생각해보니 최댓값을 가지기위해서는 최대한 많은 잔을 먹어야하기 때문에

결국 2칸이라는 조건은 동일하게 존재한다고 생각해도 무방하다

 

이전에 작성한 코드를 보면서 작성하다가, 마지막 잔을 꼭 먹어야하는건 아니니까...뭐가 다를까 생각해보았다

마지막 잔을 꼭 먹어야한다는 점이 없기 때문에 result리스트에 값을 저장할 때 계단 오르기에 썼던

위치의 값들 뿐만 아니라 이전 index의 result리스트 값도 저장해야한다는 점을 알 수 있었다

다시 말하자면, 이전 문제에서는 result 리스트의 값이 [6, 16, 23, 28, 33, 32]와 같이 나오지만,

이 문제에서는 [6, 16, 23, 28, 33, 33]처럼 나와야한다 마지막 잔을 꼭 먹어야한다는 조건이 없기 때문이다

 

이를 반영하여 코드를 작성하면 된다(2579 계단 오르기 코드 참고)

num = int(input())
wine = []

for _ in range(num):
    wine.append(int(input()))
    
if num == 1:
    print(wine[0])
elif num == 2:
    print(sum(wine))
else:
    result = [0] * num
    result[0] = wine[0]
    result[1] = result[0] + wine[1]
    result[2] = max(wine[1] + wine[2], wine[0] + wine[2])
    
    for i in range(3, num):
        result[i] = max(result[i-2] + wine[i], result[i-3] + wine[i-1] + wine[i])
    
    # print(result)
    print(result[-1])