問題

016 - Minimum Coins（★3）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programmi

方針

• 合計枚数は9999枚以下
  • 9999までfor
• aの枚数をi枚とすると、bとcの枚数の合計は、9999 - i枚
• ありえないときは、早期リターン

コード

python
n = int(input())
a, b, c = map(int, input().split())
ans = pow(10, 18)
for i in range(10000):
    if a * i > n:
        break
    for j in range(10000-i):
        if a * i + b * j > n:
            break
        if (n - (a * i + b * j )) % c == 0:
            k = (n - (a * i + b * j )) / c
            ans = min(ans, i+j+k)
 
print(int(ans))