백준 16194번 카드 구매하기 2 C++

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

 

https://kjhcocomi.tistory.com/11

백준 11052번 카드 구매하기 C++

이 문제와 유사한 문제이다. 금액의 최대가 아닌 최솟값을 구하면 된다.

여기서는 최솟값을 구해야 하기 때문에 초기값을 넣어주어야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

const int INF = 987654321;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<int> cards(n + 1);
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> cards[i];
		dp[1][i] = i * cards[1];
		dp[0][i] = 0;
		dp[i][0] = 0;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (j - i < 0) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = min(dp[i][j - i] + cards[i], dp[i - 1][j]);
			}
		}
	}
	cout << dp[n][n];
};