Time for Change

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int t = 5;
    10    while (t--) {
    11        int n, m; cin >> n >> m;
    12        vector<int> coin(m);
    13        for (int i = 0; i < m; i++) {
    14            cin >> coin[i];
    15        }
    16        vector<int> dp(n + 1, inf);
    17        dp[0] = 0;
    18        for (int x : coin) {
    19            for (int i = x; i <= n; i++) {
    20                dp[i] = min(dp[i], dp[i - x] + 1);
    21            }
    22        }
    23        cout << dp[n] << '\n';
    24    }
    25    return 0;
    26}