硬貨の問題
硬貨の問題(プログラミングコンテストチャレンジブック p42)
1円玉、5円玉、10円玉、100円玉、500円玉が、それぞれ枚ずつある。できるだけ少ない枚数の硬貨でA円を支払うとき、何枚の硬貨を出す必要があるか。
制約
アルゴリズム
なので、大きい硬貨から優先的に使用する貪欲法で解ける。
コード
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(); } }