coin_problem.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define rep(n, i) for(int i = 0; i < n; i++)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

void solve(void){
    int n, m;
    scanf("%d %d\n", &n, &m);
    int coins[m], pays[n+1];
    rep(m, i) scanf("%d ", &coins[i]);
    rep(n+1, i) pays[i] = i;
    rep(m, i){
        for (int j = coins[i]; j < n+1; j++){
            pays[j] = MIN(pays[j], pays[j - coins[i]]+1);
        }
    }
  printf("%d\n", pays[n]);
}

int main(void){
  solve();
  return 0;
}