[伯俊]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)
Reference
この問題について([伯俊]11047硬貨0), 我々は、より多くの情報をここで見つけました https://velog.io/@saessak/백준-11047-동전-0テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol