이번 문제는 다이나믹 프로그래밍으로 해결하였다. 우선 카드 i개를 구매하는 최소 비용을 구해보면 cards[1]+dp[i-1], cards[2]+dp[i-2], cards[3]+dp[i-3], ... , cards[i]+dp[0]이 된다. 그러므로 점화식은 dp[i]=cards[j]+dp[i-j]가 된다. 이 중에서 최솟값으로 계속 갱신하면 dp[i]에 i개를 구매하는 최소 비용이 저장되게 된다.

• n을 입력받는다.
• 카드팩의 금액을 cards배열에 입력받는다. 이때 맨 앞에 0을 먼저 넣고 입력받아 인덱스가 헷갈리지 않도록 한다. (1부터 시작으로 간주)
• dp를 False n+1개로 채운다. 최솟값을 구하기 위해 False로 초기화하였다.
• 1부터 n까지의 i에 대한 for문을 돌린다.
  -> 1부터 i까지의 j에 대한 for문을 돌린다.
  --> 만약 dp[i]가 False라면 dp[i]를 dp[i-j]+cards[j]로 갱신한다.
  --> 그 외에는 dp[i]를 dp[i]와 dp[i-j]+cards[j] 중 더 작은 것으로 갱신한다.
• dp[n]을 출력한다.

Code

n=int(input())
cards=[0]+list(map(int, input().split()))
dp=[False]*(n+1)
for i in range(1,n+1):
    for j in range(1, i+1):
        if dp[i]==False:
            dp[i]=dp[i-j]+cards[j]
        else:
            dp[i]=min(dp[i], dp[i-j]+cards[j])
print(dp[n])