BAEKJOON 5585小銭👛
6434 ワード
アルゴリズムの第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を使用するのは、処理速度を速めるためです.答え方は以下の通りです.
入力した値はString形式で入力されるのでInteger.ParseIntを使用してint形式に変換します.
こんな満足感でコードしてるんだろうなぁ~今から次の問題を解くぞハハハ
Reference
この問題について(BAEKJOON 5585小銭👛), 我々は、より多くの情報をここで見つけました https://velog.io/@yeonjae/BAEKJOON-5585번-거스름돈テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol