BAEKJOON 5585小銭👛


アルゴリズムの第3週の第1題!!


👛 グリディアルゴリズム<お金を探す問題>👛
📌Gredyアルゴリズムとは?グリディアルゴリズムは簡単だが強力な問題解決方法である.名前から分かるように、どんな問題があっても、単純に無知で、貪欲に問題を解くアルゴリズムです.ここで貪欲は「今の状況では、今すぐ良いものを選ぶ方法」を意味する.

グーグルの時に一番分かりやすい画像を持ってきました.上の写真を一緒に見ると、7について行くと107という数字になりますが、13について行くと24という数字になります.遠くから見ると、7に従うのが有利だと思うかもしれませんが、グリディアルゴリズムは現在与えられている状況でしか考えられないので、13についていきます.->これがグリディアルゴリズム=目の前の利益に追随する
幸いなことに,符号化テストで主に発生する問題の1つとされるGRADYアルゴリズム学習では,これらの問題を処理できる!代表的なおつり問題を解決しました!
標準問題リンクhttps://www.acmicpc.net/problem/5585

最大の通貨単位からお金を探すのがポイントです.私が説明したコードは以下の通りです.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Change_5585 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 거스름돈 알고리즘
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int pay = Integer.parseInt(br.readLine());
		int coin[] = {500,100,50,10,5,1};
		int count = 0;
		int change = 1000 - pay;
		for(int i=0;i<coin.length;i++) {
			count += change / coin[i];
			change = change % coin[i];
		}
		System.out.println(count);
	}
}
スキャナ入力値を使用せずにBufferReaderを使用するのは、処理速度を速めるためです.
答え方は以下の通りです.
  • BufferReaderで支払いが必要な値を入力します.
    入力した値はString形式で入力されるのでInteger.ParseIntを使用してint形式に変換します.
  • ヘッダの単位を配列に格納します.
  • のヘッダの個数をデフォルト値0に設定します.
  • 100ウォンから支払うべき給与を差し引いた小銭を変動変数に預けます.
  • for文を使用して、配列に格納された小銭の単位で計算を繰り返します.-小銭単位の整数値をcountに加算します.小銭の端っこを小銭にかえる.
  • for文がすべて回転した後、countの値を出力します.
  • 私の答えはこうです.私より速いコードがあるかもしれませんが、私はそれを見に行くべきです.ほほほ、グーグルと他の人のコードを見ないで解読に成功しました.🎈
    こんな満足感でコードしてるんだろうなぁ~今から次の問題を解くぞハハハ