競プロ典型90問：016 - Minimum Coins（★3）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_p

挑戦結果

• 結果：できた
• 時間：5分ぐらい

考えたこと

• 三重ループで全列挙。ループのネスト条件をだんだん狭くするやつ。
• サンプル問題が帰ってこなかった。
• 最後は計算すればループが不要になることに気がついた
• とはいえサンプル問題をPythonで動かすと数秒かかる。pypyなら通るか？

公式解説

https://twitter.com/e869120/status/1383189464650981378

解説を読んだふりかえり

• 割とするっとはとけたけど、トライ＆エラーが結構有った。最初から二重ループを思いつけると良かった。

ソース

N = int(input())
A,B,C = [int(x) for x in input().split()]

cnt = 999999
for a in range(10000):
    for b in range(10000-a):
        if (N - (A*a + B*b)) % C == 0:
            c = (N - (A*a + B*b)) // C
            if c>=0:
                cnt = min(cnt, a+b+c)

print(cnt)