このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
ポイント
各コインの使用枚数を全探索で求めていきたいところですが、9999枚分のfor loopを3重にする
下記の様なコードではTLEとなってしまいます。
for a in range(9999):
for b in range(9999):
for c in range(9999):この問題のポイントは、上記全探索の処理時間をどのように短縮させるか、言い換えれば全探索の無駄をどのように省くかという点です。
ここで無駄となっているのはCの使用枚数を求める3行目のfor loopです。
A,Bの使用枚数が決まれば、Cの使用枚数は(N - A * A使用枚数 - B * B使用枚数）÷ C
で求めることができます。
※-尚、ここで余りが出てしまう場合ちょうどN円を支払うことはできません。
最後のfor loopを削除し、代わりに計算式を入れておけば制限時間内に処理が完了します。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N = int(input())
A, B, C = map(int, input().split(" "))
ans = 9999 # 回答の初期値は問題文の条件より9999枚
# 全探索
for use_a in range(ans): # Aの使用枚数をansとすることで回答が更新されるたびループ回数が短くなる
for use_b in range(ans - use_a):
use_c = (N - (A * use_a + B * use_b)) // C # この式だとuse_cがマイナスになる場合、余りが出る場合があるので次のif文でこれらを弾く
if A * use_a + B * use_b + C * use_c == N and use_c >= 0:
ans = min(ans, use_a + use_b + use_c)
print(ans)
if __name__ == '__main__':
main()
