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;
}