[CSES] Minimizing Coins

Minimizing Coins

문제

https://cses.fi/problemset/task/1634/

CSES - Minimizing Coins

 

요약 

주어진 동전을 활용해 목표합을 만들 때, 가장 적은 동전의 수를 활용하여 만들기

이때, 사용된 동전의 수를 출력한다.

 

CODE

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=100, mxX=1e6;
int n, x, c[mxN+1];
int dp[mxX+1];

int main() {
	cin >> n >> x;
	for(int i=0; i<n; i++) {
		cin >> c[i];
	}
	
	for(int i=1; i<=x; i++) {
		dp[i]=1e9;
		for(int j=0; j<n; j++) {
			if(i>=c[j]) {
				dp[i] = min(dp[i], dp[i-c[j]]+1);
			}
		}
	}
			
	if(dp[x]==1e9) {
		cout << -1;
	}
	else {
		cout << dp[x];
	}
}

 

점화식

if(i>=c[j]) {
	dp[i] = min(dp[i], dp[i-c[j]]+1);
}

 

 

주의 사항(스스로 조심해야 할 부분)

 

1. 점화식에 min을 사용하므로, dp[i]에 큰 값을 넣어야 한다.

dp[i] = INF;

 

2. dp 배열 할당 시, 문제를 잘 보고 알맞은 값을 넣어야함.

 

    > 할당을 올바르게 하지 않았다면, RUNTIME ERROR 를 만난다.