[BOJ] 16194 카드 구매하기 2

문제 요약 및 풀이

16194번: 카드 구매하기 2

간단한 DP 문제다.

$d[i]=카드i개를갖기위해지물해야하는금액의최솟값$

위와 같이 dp 배열을 정의하고 생각하면 당연하게도 아래와 같은 점화식이 성립한다.

for j in range(i)
  d[i] = min(d[i], d[i - j] + d[j])

풀이 코드

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])

끝