문제

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

나의 코드 (답안 참조)

"""
1. 아이디어
이중 반복문을 통해 i개의 카드를 구매할 시점에 제일 비싸게 살 수 있는 경우를 dp에 누적한다.

2. 시간복잡도
O(2n(n-1)) 정도?
"""

"""
dp[1] = 1을 만드는 방법은 1번 카드 1개를 쓰는 방법뿐이다.
dp[2] = 2를 만드는 방법은 2번 카드 1개, 혹은 1번 카드 2개를 쓰는 것 중 큰 수 이다.
dp[3] = 3을 만드는 방법은 3번 카드 1개, 혹은 1과 dp[2]를 쓰는 것 중 큰 수이다. 여기서 1,1,1로 3을 만드는 경우, 1,2로 3을 만드는 경우는 dp[2]에서 처리가 끝난 것이다.
dp[n] = n을 만드는 방법은 n번 카드 1개, 혹은 1과 dp[n-1], 혹은 dp[2]와 dp[n-2], ..dp[i]와 dp[n-i]를 만드는 것 중 중 큰 수이다.
"""

from sys import stdin
input = stdin.readline

n = int(input())
p = [0] + list(map(int, input().split()))
dp = [0] * (n+1)

for i in range(1, n+1):
    for j in range(1, i+1):
        # dp[i] = 카드 i개 구매하는 최대 가격, p[j] = j개가 들어있는 카드팩 가격
        dp[i] = max(dp[i], dp[i-j] + p[j])

print(dp[i])

    

느낀점

쉬운 문제인 듯 하면서도 잘 안풀리는 문제