문제 요약 및 풀이
간단한 DP 문제다.
\[d[i] = 카드 i 개를 갖기 위해 지물해야 하는 금액의 최솟값\]위와 같이 dp 배열을 정의하고 생각하면 당연하게도 아래와 같은 점화식이 성립한다.
1
2
for j in range(i)
d[i] = min(d[i], d[i - j] + d[j])
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
INF = 123456789
n = int(input())
l = [0, *map(int,input().split())]
d = [INF for _ in range(n + 1)]
for i in range(n+1):
d[i] = l[i]
for j in range(i):
d[i] = min(d[i], d[i-j] + d[j])
print(d[n])
끝