동전2

 

*dp 배열을 2차원으로 정의하는데, 

dp[i][j] = i번째 동전을 이용해서 j원을 만드는데 사용하는 최소 동전 사용 횟수 

*동전들을 오름차순으로 정렬한다.

*제일 가치가 작은 동전이 k보다 크면 불가능한 경우이다. (-1)

*2차원 반복문에서 1원부터 k원까지 확인하는데, 각 조합을 구하는 경우가 3가지로 나뉘어진다.

1. i원이 j번째 동전으로 나뉘어 떨어질때 -> i/coin[j] 가 최소가 될 수 있다. 

2. j번째 동전을 사용했을 때 -> dp[j][i-coin[j]]+1

3. j번째 동전을 사용하지 않았을 때 -> dp[j-1][i]

 

테스트케이스

3 13
1
5
12
ans = 2

2 100
7
8
ans = 13

3 24
1
7
10
ans = 3

3 15
1
5
12
ans = 3

3 11
1
5
12
ans = 3

 

#include <iostream> #include <vector> #include <algorithm> #define INF 987654321 using namespace std; int coin[101] = { 0 }, dp[101][10001] = { 0 }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; int ans = INF; for (int j = 0; j <= n; j++) { for (int i = 1; i <= k; i++) { dp[j][i] = INF; } } for (int i = 1; i <= n; i++) { cin >> coin[i]; } //한가지 종류의 동전을 사용해서 만들 수 있는 경우는 했음 //조합을 이용했을 때 k원이되는 조합을 찾느다. (중복 조합 안됨) //dp[i][j] = i번째 동전을 사용해서 만들 수 있는 j원일 때 최소 동전 사용 횟수 sort(coin + 1, coin + n + 1); //오름차순으로 정렬한다. if (coin[1] > k) { cout << -1 << '\n'; return 0; } for (int i = 1; i <= k; i++) { for (int j = 1; j <= n; j++) { if (i >= coin[j]) { if (i % coin[j] == 0) { dp[j][i] = min(dp[j][i], i / coin[j]); } dp[j][i] = min(dp[j][i], dp[j][i-coin[j]]+1); } dp[j][i] = min(dp[j][i], dp[j-1][i]); } } for (int i = 1; i <= n; i++) { ans = min(ans, dp[i][k]); } if (ans == INF) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }