AOJ : 1028 - ICPC: Ideal Coin Payment and Change
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1028&lang=jp
日本語の問題文があるので省略です
アルゴリズム
P 以上の価格で, 自分が払う価格 X を先に決定してしまいます.
X を決定すれば, その価格 X をちょうど支払うための最小の枚数と, 返ってくるおつり (X - P) の最小枚数を一意に決定づけることができます.
価格 X の上限は, 自分が持っている小銭で支払える価格の上限にします.
おつりの最小枚数は, 500円玉から順番に, 貪欲法により求まります.
あと, 何も工夫せずこのまま提出するとギリギリTLEが出てしまったので, おつり計算をメモしておいて再利用するようにしました(ソースコード中のchangeMemo).
プログラム
#include <iostream> #include <cstdio> using namespace std; int p,n[6]; int m[] = {1,5,10,50,100,500}; int changeMemo[1000001]; //最小の釣銭の枚数を返す int change(int x){ int res = 0; for(int i=5;i>=0;i--){ res += x / m[i]; x -= m[i] * (x / m[i]); } return res; } //自分が持っている硬貨で価格をちょうど支払えるかの判定 int pay(int x){ int res = 0; for(int i=5;i>=0;i--){ int tmp = x / m[i]; if(tmp <= n[i]){ res += tmp; x -= m[i] * tmp; } else{ res += n[i]; x -= m[i] * n[i]; } } return x==0 ? res : -1; } int main(void){ while(scanf("%d",&p),p){ int sum = 0; //自分が支払える上限 for(int i=0;i<6;i++){ scanf("%d",&n[i]); sum += n[i] * m[i]; } int ans = 999999999; //自分が支払う額を決める for(int i=p;i<=sum;i++){ int tmp = pay(i); //支払可能ならば, 支払枚数とおつり枚数で最小値を更新する if(tmp != -1){ if(i!=p){ if(changeMemo[i-p]==0) changeMemo[i-p] = change(i-p); tmp += changeMemo[i-p]; } if(ans > tmp) ans = tmp; } } printf("%d\n",ans); } return 0; }