11052 카드 구매하기

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

N = int(input())
card_list = [0]
card_list += list(map(int,input().split()))
dp_table = [0]*(N+1)
dp_table[1] = card_list[1]

for n in range(2,N+1):
    temp = card_list[n]
    for p in range(1,n):
        temp = max(temp,card_list[p]+dp_table[n-p])
    dp_table[n] = temp

print(dp_table[-1])

3. 문제 풀이

이 문제는 점화식을 쓰지만.. 이중 for문을 써야하는 문제였다. 왜냐하면 dp table의 각 요소들은 n개의 카드를 뽑을 때, 가장 최대의 비용을 기록한 곳이다. 그러나 한장을 더 뽑을때마다 이전 요소에 +1을 하는, 즉 $P_1$을 더하는게 최대가 아닐 수 있다. 따라서 해당 카드의 수를 뽑을 수 있는 모든 경우의 수를 다 살펴봐야했고, 이를 이중 for문을 사용해서 구현해야한다.