[백준] 카드 구매하기2 16194번 C++ 풀이

 

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

16194번: 카드 구매하기 2

#include <iostream>
#include <algorithm>
using namespace std;
int arr[10001];
int dp[10001];
int N;
int main(void)
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	for (int i = 1; i <= N; i++) // 총 i장을 살거야
	{
		dp[i] = arr[i]; // i장살때 기본으로 i장든거 사는걸 초기값
		for (int j = 1; j <= i; j++) // i장중 j장은 따로 살거야
			dp[i] = min(dp[i], dp[i - j] + dp[j]);
		/* 위 줄은 i장을 살때 그냥 i장을 사는게 쌀까 ?
		* i-j장 최소비용+j장 최소비용이 쌀까 ? 비교하는것
		*/
	}
	cout << dp[N];
}