質問する

ジュンギュが持っているコインは全部でN種類で、どれもたくさんあります.
硬貨を適当に使って、その価値の和をKにします.必要なコインの数の最大値を求めるプログラムを作成してください.
入力
第1行はNとKを与える.(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
2行目から、N行目では昇順にコインの価値Aiが与えられる.(1≦Ai≦100000,A 1=1,i≧2の場合、AiはAi-1の倍数)
しゅつりょく
Kドルを作るのに必要なコインの数の最大値を1行目に出力します.
BOJ11047

に近づく

これはグリディアルゴリズムの最も代表的な問題である.入力されたコインの種類では、大きなコインから元金を差し引き、数えて解決します.

コード#コード#

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int [] coin = new int[n];
		for(int i = 0; i<n; i++) {
			coin[i] = sc.nextInt();
		}
		
		int count = 0;
		for(int i = n-1; i>=0; i--) {
			if(k >= coin[i]) {
				count += (k/coin[i]);
				k %= coin[i];
			}
		}
		
		System.out.println(count);
	}
}