アルゴリズム問題14916解答

質問する

春香はコンビニのカウンターで働いています.お客さんは2元と5元の小銭しかありません.2元の硬貨と5元の硬貨は無限に多い.コインの個数は最小限にしなければならない.おつりがnなら、最小コインの個数を教えてくれるプログラムを書いてください.
例えば、15元なら5元3個、14元なら5元2個、2元2個の計4個、13元なら5元1個と2元4個の計5個、硬貨の個数が一番少ない.

コア

問題の核心は、ボイコットするコインの数をできるだけ減らすことだ.コインの個数を最低にするにはどうすればいいですか?おつりを最大額のコインに入れて、それより小さい額のコインに入れます.
今から問題を見てみましょう問題はおつりがnです.そして、私たちはお客様の要求に従って、2元硬貨と5元硬貨で小銭を探すしかありません.私たちは無限の2元5元硬貨を持っています.いくら探しても1つしか探せません.しかし、取り戻した硬貨の数をできるだけ減らすため、上記の方法で5円硬貨が一番多い場合は、残りの小銭は2円硬貨で埋めます.
数式で表現しましょう.
ではnはおつりで、xは5元硬貨の個数yは2元硬貨の個数です.
式:n=5 x+2 y.ここで私たちが探している小銭が多ければ多いほど、5元のほうがいいです.つまり、一番いい場合は、n元の小銭だけを探します.この場合,nを5で割ったと言える.すなわち、n%5=0(このとき%は余剰を求める符号)であり、nを5で割って余剰を0とする.
しかし、nは必ず5で割るとは言えない.この時、私たちは残りの小銭を2元に集めなければなりません.再表現すると、nを5で割ると、残りは0ではなく、1から4のうちの1つになります.では、おつりnは5元で、残りの2、4は2元で記入すればいいです.しかし、残りが1か3であれば、2円玉で満たすことはできません.では、5元のコインを少なくして、残りのお金を2元で揃えるようにします.この原理を応用して問題を解きましょう.

		#include<iostream>
		using namespace std;
		int main()
		{
			int n, x, y;
			cin >> n;
			x = n / 5 ; //우리가 거슬러 줘야하는 동전의 개수
			y = 0;
			while(((n - 5 * x) % 2) != 0) { // 나머지를 2으로 나누어서 0으로 떨어지면 while문을 탈출, 아니면(나머지가 1혹은 3이면) x를 감소하고 다시 계산
				if (x == 0) {  //문제가 n=1,3, 등등 안 나누어 떨어지는 경우가 생기면 x가 0이될때까지 while문을 돌것이다. 이 경우 앞의 while 조건식에서 조건식을 만족하여 if 문으로 진입한것이므로, 5원짜리 동전으로 몇개를 빼든 2원짜리 동전으로 채울 수 없다. 즉, 거스름돈을 거슬러 줄 수 있는 방법이 없는것 -> 종료하는 것이 맞다.
					printf("-1");
					return 0;  
				}
				x--;
			}
			y = (n - 5 * x) / 2;  
			printf("%d", x + y);		
		}

条件文は重複文を設定し、残りを2に分割し、文が終了した場合、または(残りが1または3の場合)xを減らして再計算します.次回は中でおつりnが5元か2元でも離れない数字であれば、-1を出力し、強制的に退出します.
上のリングを通ってwhileゲートを脱出すると、探していたnが5元と2元に分かれていることを意味します.(文中の条件で設定)したがって、x値でy値を求めることもできるし、x+y値を求めることもできる.
n=1と入力した場合

n=2と入力した場合

に感銘を与える

個人がこの問題を解決する際に出会った問題は2つある.
1.whileゲートを通過する小銭nをゼロ以外で割った場合の条件を決定する->x=0は5元ではなく、前のwhileゲートで2で割ったり、-1を出力で割ったりしない
2.while文でbreak以外の解決策を探る(while文にif文が設定されているため、breakは最大while文に逃げるしかない.そのため、問題の要求に応じて、-1を出力した後もx+y値は出力される)->-1となり、breakではなく0を返す完全なプログラムを使用してコマンドを終了する.コードがif文に入ると、-1は出力後にreturn 0に遭遇し、続行せずに終了します.