백준 20162 간식 파티 Python

문제풀이

1. 배열 자료구조인 dp에 n번째 음식의 만족도를 담습니다. 즉, dp[i]는 i번째 음식의 만족도입니다.

2. 배열 자료구조인 dp2에는 n번째 음식을 먹었을 때의 만족도의 최댓값을 담습니다. 즉, dp2[i]는 i번째 음식을 먹었을 때의 만족도의 최댓값입니다.

3. dp2의 요소는 다음과 같은 과정을 통해 얻습니다.

3-1. n번째 음식의 인덱스를 n, 만족도를 nth라 할때, dp의 n번째 이전의 요소들 중 nth보다 작은 값들에 해당하는 dp2의 요소를 모읍니다.

3-2a. 위 과정에서 모은 요소들 중 최댓값+nth가 dp2[n]이 됩니다.

3-2b. 위 과정에서 모인 요소가 없다면, n번째 이전에 먹을 것이 없다는 의미이므로 dp2[n]은 nth가 됩니다.

 

** dp의 이름을 별 생각없이 dp로 지었는데, dp2가 실질적으로 메모리제이션이 이루어지는 배열이고, dp는 동적프로그래밍과 큰 관련이 없습니다.

Python Code

import sys
readline = sys.stdin.readline
 
def main(n):
    nth = int(readline())
    #n 번째 음식의 만족도
    dp = [nth]
    #n 번째 음식을 먹었을 때의 만족도의 최댓값
    dp2 = [nth]
 
    for _ in range(n-1):
        nth = int(readline())
        # 앞의 음식 중 먹을 수 있는 음식들을 먹었을 때의 만족도의 최댓값들
        tmp = []
        for i,v in enumerate(dp):
            if v < nth:
                tmp.append(dp2[i])
        dp.append(nth)
        if tmp:
            dp2.append(max(tmp)+nth)
        # 먹을 수 있는 게 없으면, 이번 음식만 먹는 것이 최댓값
        else:
            dp2.append(nth)
    print(max(dp2))
 
if __name__ == '__main__':
    n =int(readline())
    main(n)

문제 링크

20162번: 간식 파티