Hit the Lottery [ Codeforces Round #492 (Div. 2) A ]

codeforces.com

問題

口座の n 円を 1,5,10,20,100 円ずつ引き出す。
残高を 0 円にするためには、最小で何回引き出せばよいか。

考察

600点（下から2番目の難易度）なのにタグにDPとあり、心構えをして臨んだら制約に n<=10^9 とあって、やっぱりDPではないのでは……と思って問題文を見ると、ただの両替問題でした。コイン問題ではなかったです。

両替問題なのかコイン問題なのかは、小さい順に単位を並べていったときに順番に倍数になっているかどうか、で判定できます。今回は 1,5,10,20,100 と小さい順に倍数になっているので、両替問題というわけですね。

コード

void solve (FastScanner in, PrintWriter out) {
	
	int[] money = {100,20,10,5,1};
	int n = in.nextInt();
	int ans = 0;
	for (int i=0; i<5; i++) {
		ans += n/money[i];
		n %= money[i];
	}
	
	out.println(ans);
	
}