典型90 016 – Minimum Coins（★3）

競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色！

今のレートは茶色です。

問題

典型90 016 – Minimum Coins（★3）を解きました。

考察

全探索を普通に行う場合、計算量はO(N^3)になるため、全く間に合わない。

一方で、A円硬貨とB円硬貨の2枚の枚数が定まれば、C円硬貨の枚数も自然と定まるため、O(N^2)で効率的に全探索を行うことができる。

このような、「全探索を効率的に行う方法を探す」という典型問題。

コード

N = int(input())
A, B, C = map(int,input().split())

ans = pow(10, 18)
for a in range(10000):
    if A*a > N:
        break
    for b in range(10000-a):
        if A*a + B*b > N:
            break

        if (N - (A*a + B*b)) % C == 0:
            c = (N - (A*a + B*b)) / C
            ans = min(ans, a+b+c)

print(int(ans))

まとめ

A,B,Cがコインの枚数だと誤読したせいでかなり時間がかかった…。

コンテストででたら確実に早解きゲームになる類の問題なので、ちゃんと読まなきゃ…。