백준 16194 : 카드 구매하기 2

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

16194번: 카드 구매하기 2

 

11052번과 비슷한 문제였습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 97654321
int main() {
	int n, p[1001] = { 0 }, dp[1001];
	memset(dp, INF, sizeof(dp));
	dp[0] = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			dp[i] = std::min(dp[i], dp[i-j] + p[j]);
	printf("%d", dp[n]);
}