(Python/🥈4)백준 알고리즘 11047번: 동전 0

 

문제 바로가기 

백준 알고리즘 동전 0

 

문제:

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력:

 

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력:

 

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

풀이 :

나는 두 가지 방법으로 풀어봤다.

 

1. 오름차순

import sys

N,M= map(int, input().split())

lst = [int(sys.stdin.readline().rstrip()) for i in range(N)]
count = 0

if M < lst[0]:
    print(0)

else:
    num = N-1
    while num >= 0:
        if M >= lst[num]:
            count += M // lst[num]
            M %= lst[num]
        num -= 1
print(count)





lst =[1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]

 

조심해야 할 점이 있다.

바로 첫 번째 동전의 가치가 M보다 큰 경우에 대한 처리를 해줘야한다. 따라서 첫 번째 동전의 가치가 M보다 큰 경우에는 해당 동전을 사용할 수 없으므로 필요한 동전 개수의 최솟값은 0이 되어야 한다.

 

두 번째 

 

 

 

N, M = map(int, input().split())

coins = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
coins.sort()  # 동전의 가치를 오름차순으로 정렬

count = 0

for coin in coins:
    while M >= coin:
        count += 1
        M -= coin

print(count)


포문
for coin in coins:
    if M >= coin:
        count += M // coin
        M %= coin

 

아마 이게 저석이 아닐까 싶다 오름차순으로 나열후 포문을 돌리는 것이다.

 

포문을 밑에 둘 중 하나를 하면 될것 같다.