【二重ループ：活用編 三角形の探索】STEP: 7 お金の支払い (paizaランク C 相当) 解答例 – PHP編【二重ループメニュー】
【二重ループメニュー】 > 【二重ループ：活用編 三角形の探索】STEP: 7 お金の支払い (paizaランク C 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
かなり難しかった印象の問題です。答えが分かった後に振り返ってみると、ただの全通りの検査問題なのですが、「最小の枚数 = 大きい金額の硬化をできるだけ使う」という先入観に捉われるとドツボにハマる問題に感じます(;^ω^)
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
<?php $input = explode(" ",trim(fgets(STDIN))); $x = $input[0]; $y = $input[1]; $price = $input[2]; $counter = 0; $min = 1500; for($i = 0;$i < 1500;$i++){ for($j = 0;$j < 1500;$j++){ $counter = 0; $money = $price; $test1 = $i * $y; $test2 = $j * $x; if($money >= $test1){ $money = $money - $test1; } if($money >= $test2){ $money = $money - $test2; } $counter = $money + $i + $j; if($counter < $min){ $min = $counter; } } } echo $min; ?> |
解答方針
大きな硬貨で払えるだけ払う操作を繰り返すことで最小枚数を導けそうですが、下の例のように必ずしも「大きな硬化を使用する ＝ 最小枚数」という事ではないことが分かります。
1 円 , 7 円 , 16 円 で 21 円を支払い
・大きな金額から支払った場合
16 円 1 枚
1 円 5 枚
・最小枚数で支払った場合
7 円 3 枚
よって全通りの硬化の支払いパターンを処理し、その中から最小の枚数を探し出します。
硬化Xの枚数を$i、硬化Yの枚数を$jとして、二重ループを回します。一円硬化の枚数は「Z – (X * $i) – (Y – $j)」で求めることができます。そして「Z + $i + $j」の値が最も小さいものを探し出す問題です。
また問題の条件、「 2 ≦ X , Y ≦ 1000」と「1 ≦ Z ≦ 3000」であることから、仮に最も大きい支払額3000円の時、最低でも2円硬化が存在することから、支払い枚数の最小値は「1500」以下であることが分かるので、ループ回数は1500回、回せばいいと考えることができます。
硬化の情報と支払情報を取得する
|
1 2 3 4 5 6 |
$input = explode(" ",trim(fgets(STDIN))); //標準入力値をexplodeで分割して配列に格納する $x = $input[0]; //X円硬化 $y = $input[1]; //Y円硬化 $price = $input[2]; //支払い金額 $counter = 0; //合計硬化枚数のカウント用変数 $min = 1500; //最小硬化枚数を入れる変数 |
二重ループによる全検索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
for($i = 0;$i < 1500;$i++){ for($j = 0;$j < 1500;$j++){ $counter = 0; //硬化枚数の初期化 $money = $price; //「$money」という変数に支払い額を代入する（初期化） $test1 = $i * $y; //Y硬化「$i」枚の金額 $test2 = $j * $x; //X硬化「$j」枚の金額 if($money > $test1){ //もし「$test1」が支払額以下なら $money = $money - $test1; //X硬化の合計金額分、支払額から差し引く（更新する） } if($money >= $test2){ //もし「$test2」が支払額以下なら $money = $money - $test2; //Y硬化の合計金額分、支払額から差し引く（更新する） } $counter = $money + $i + $j; //硬化の合計枚数をカウントする if($counter < $min){ //もし「$counter」が「$min」より小さかったら $min = $counter; //最小値を更新する } } } |
あとは検証した硬化枚数が、今まで検索したものより小さかったら「$min」に代入していけば最小値を求めることができます。
