[python/파이썬] 백준 20162 간식 파티

[문제 출처]

https://www.acmicpc.net/problem/20162

20162번: 간식 파티

 

[문제 풀이]

일반적인 dp 문제라고 생각해서 지금 까지랑 비슷하게 풀었는데 잘 풀리지 않아 다른 풀이를 참고했다.

풀어본 방법과는 다른 방식으로 풀어야 풀리는 문제인 것 같은데 다른 풀이도 다양하지 않아서 정확히는 모르겠다.

 

import sys
input = sys.stdin.readline
 
n = int(input())

snack = int(input())
dp = [snack]
dp2 = [snack]
 
for _ in range(n-1):
    snack = int(input())
    
    tmp = []
    for i,v in enumerate(dp):
        if v < snack:
            tmp.append(dp2[i])
    dp.append(snack)
    if tmp:
        dp2.append(max(tmp)+snack)
    else:
        dp2.append(snack)
    
print(max(dp2))