[백준 16194 / C++] 카드 구매하기 2

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

---

위의 문제와 똑같은 문제이지만 최솟값을 찾는 문제이다. 

다른점은 dp의 초기 세팅을 cost로 해주는 점과 max 알고리즘 대신에 min으로 바꿔줬다. 

 

11052번 문제를 풀지 않았다면 위의 링크를 들어가서 풀고나서 이 문제를 풀기를 추천한다. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; 

int main() {
	int n; cin >> n; 
	vector <int> cost(n + 1); 
	vector <int> dp(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> cost[i]; 
		dp[i] = cost[i]; 
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i] = min(dp[i], dp[i - j] + cost[j]); 
		}
	}
	cout << dp[n]; 
}

 

16194번: 카드 구매하기 2