Problem 1028 : ICPC: Ideal Coin Payment and Change

Problem J: ICPC: Ideal Coin Payment and Change
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1028&lang=jp

• 問題概要

それぞれの種類の金額のコインの枚数が与えられる。払いたい金額も与えられる。
どのように払えばお釣りと支払いにつかうコインの合計は最小になりますか。

• 解法

店員さんに渡すお金が定まれば、渡す枚数受け取る枚数が定まるので、
払いたい金額より多めのとこまでそれぞれの場合さがしてやればみつかる

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

int t[6], coin[] = {500, 100, 50, 10, 5, 1};

int change(int c){
  int cnt=0;
  rep(i, 6){
    if(c >= coin[i]){
      cnt += c/coin[i];
      c %= coin[i];
    }
  }
  return cnt;
}

int buy(int c){
  int cnt = 0;
  rep(i, 6){
    if(c >= coin[i]){
      int tmp = min(c/coin[i], t[i]);
      cnt += tmp;
      c -= coin[i] * tmp;
    }
  }
  if(c != 0)cnt = 900000;
  return cnt;
}

main(){
  int p;
  while(cin >> p){
    int sum = 0;
    rep(i, 6)cin >> t[i];
    reverse(t, t+6);
    if(p == 0)break;
    int ans = 900000;
    REP(i, p, p + 1000)ans = min(ans, buy(i) + change(i - p));
    cout << ans << endl;
  }
}

changeというのはお釣りにつかうコインの枚数を求める関数。
buyというのは購入時につかうコインの枚数を求める関数。