[伯俊]11047硬貨0


📌質問リンク


11047硬貨0

💡 問題を解く


入力条件で硬貨の価値Ai,A 1=1,i≧2の場合,AiはAi−1の倍数であり,最大価値の硬貨から個数を計算することで最適解が保証される.
例えば、コインの価値(通貨単位)が500元、400元、100元の場合、800元を作ろうとするとベスト年数は2(400+400)ですが、GRIDアルゴリズムは4(500+100+100+100)です.
しかし、コインの価値は相互倍数の形なので、価値の大きい単位から計算すると、最適な年が保証されます.

📋コード#コード#


参考書コード
# 11047 동전 0
n, k = map(int, input().split())
coin = []
count = 0  # 동전의 개수를 저장할 변수

# 동전의 가치 입력받음
for i in range(n):
    coin.append(int(input()))

# 동전의 가치가 오름차순으로 주어지므로 뒤에서부터 계산
for i in range(n-1, -1, -1):
    count += k // coin[i]  # k원에서 현재 단위만큼 나눈 몫을 더함
    k %= coin[i]  # 나머지를 구해 다음 단위에서 계산함

print(count)