eynizadeMurad

Minimum number of coins to form given sum

Sep 23rd, 2017
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fast_read; ios::sync_with_stdio(0);cin.tie(0);
  3. #define INF INT_MAX
  4. using namespace std;
  5. int n,a[101],x,ans[101];
  6. int main() {
  7.     fast_read;
  8.     cin>>n;
  9.     for (int i = 1;i<=n;i++)cin>>a[i];
  10.     cin>>x;
  11.     ans[0] = 0;
  12.     for (int i = 1;i<=x;i++) {
  13.         ans[i] = INF;
  14.         for (int j = 1;j<=n;j++) {
  15.             if (i - a[j] >= 0) ans[i] = min(ans[i],ans[i - a[j]] + 1);
  16.         }
  17.     }
  18.     cout<<ans[x]<<endl;
  19.     return 0;
  20. }
Advertisement
Add Comment
Please, Sign In to add comment