백준 2294 : 동전 2 c++

코드

#include <iostream>

using namespace std;

bool compare(int a, int b){
	return a > b;
}

int main(){
	int n, k;
	int price[101];
	int dp[10001];
	
	cin >> n >> k;
	
	for(int i = 1; i <=k; i++){
		dp[i] = 10001;
	}
	
	for(int i = 0; i < n; i++){
		cin >> price[i];
		
		for(int j = price[i]; j <= k; j++){
			dp[j] = min(dp[j], dp[j-price[i]]+1);
		}
	}
	
	if(dp[k]==10001) cout << -1;
	else cout << dp[k];

	return 0;
}

알게된점

2중반복문으로 구하는 dp는 생각하기 너무 어려운 것 같다.

다음에 한번 더 풀어보면서 복습해보아야겠다.

dp[j] = min(dp[j], dp[j-price[i]]+1); 이 수식을 생각하는게 참 어려운 것 같다.