쌓고 쌓다

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

알고리즘/백준

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

승민아 2021. 12. 23. 17:11

 

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

 

16194번: 카드 구매하기 2

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

#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];
}
Comments