読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

硬貨の問題

硬貨の問題(プログラミングコンテストチャレンジブック p42)

1円玉、5円玉、10円玉、100円玉、500円玉が、それぞれC_1, C_5, C_{10}, C_{50}, C_{100}, C_{500}枚ずつある。できるだけ少ない枚数の硬貨でA円を支払うとき、何枚の硬貨を出す必要があるか。
制約
0\leq C_1, C_5, C_{10}, C_{50}, C_{100}, C_{500} \leq 10^9
0 \leq A \leq 10^9

アルゴリズム

0\leq 1 \leq 5 \leq 10 \leq 50 \leq 100 \leq 500
1+1 \leq 5
5+5 \leq 10
10+10 \leq 50
50+50 \leq 100
100+100 \leq 500
なので、大きい硬貨から優先的に使用する貪欲法で解ける。

コード

import java.util.*;
public class coin_problem {
	static Scanner scanner;
	static int[] coin;
	coin_problem(){
		coin = new int[]{1,5,10,50,100,500};
		int[] C = new int[coin.length];
		for(int i=0; i<coin.length; i++) C[i] = scanner.nextInt();
		int A = scanner.nextInt();
		System.out.println( solve(C,A) );
	}
	int solve(int[] C, int A){
		int ans = 0;
		for(int i=coin.length-1; i>=0; i--){
			int t = Math.min(A/coin[i],C[i]); //最大C[i]枚しか使えない
			A -= t*coin[i];
			ans += t;
			if(A == 0) break; //なくても良い
		}
		return ans;
	}
	public static void main(String[] args) {
		scanner = new Scanner(System.in); 
		new coin_problem();
	}
}