競プロ典型90問をRustで解いていこう（工夫した全探索）3日目

2022-03-09

Rust

はじめに

コードギアスの復活のルルーシュがPrimeVideoに入っていたので見てました。コードギアス復活のルルーシュ

TV版しか見てなかったのですが、あの死んだと思っていた人が生きてましたね。

とりあえず、今日の問題を取っていきましょう。

本日の問題

競プロ典型90問をRustで解いていこう（準備）0日目

今日は上の記事から3問目である、この問題を解いていきます。 016 - Minimum Coins（★3）を解いていこうと思います。

016 - Minimum Coins（★3）

A 円硬貨、B 円硬貨、C 円硬貨が与えられてN円支払うとき、何枚で支払いできるか　という問題です。

立てた方針

A硬貨とB硬貨で全探索して、C硬貨を求めるようなやり方を取ります。上限は10000枚としているので2つまで全探索で求めて、AとBの硬貨で支払った額の残りを求めて、 c硬貨で割れば何枚か求めれるので2重ループでいける。

三枚目の硬貨はk = (n - (a i + b j) ) / c

Rustでの回答例

あまりこの問題については言うことが無いですが、とりあえずこう書きました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
        c: usize,
    }

    let mut ans = std::usize::MAX;
    for i in 0..=9999 {
        for j in 0..=9999 {
            if n >= a * i + b * j {
                if (n - (a * i + b * j)) % c == 0 {
                    let k = (n - (a * i + b * j)) / c;
                    ans = std::cmp::min(ans, i + j + k);
                }
            }
        }
    }
    println!("{}", ans);
}

Rustで2つのうち、小さい方を求めるのはこうやります。 https://doc.rust-lang.org/std/cmp/fn.min.html