백준 파이썬 11047번: 동전 0

www.acmicpc.net/problem/11047

11047번: 동전 0

문제 유형: 그리디 알고리즘

 

# Solution 1

N, K = map(int, input().split())
coins = []
count = 0

for _ in range(N):
    coins.append(int(input()))

coins.sort(reverse=True)

for coin in coins:
    count += K // coin
    K %= coin # k = k % coin

print(count)

1. 우선 동전의 종류 개수 N과 타겟 액수 K를 입력받는다.
2. 반복문을 N번 돌며 입력 값을 coins 리스트에 저장한다.
3. 가장 큰 액수의 동전부터 거슬러가야 최소한의 동전이 사용된다. 그러므로 coins 리스트를 내림차순으로 정렬해준다.
4. 타겟 액수 K를 가장 액수가 큰 동전부터 나누기 시작해 그 몫을 동전의 총개수에 더해준다. 4200원을 1000원으로 거슬러야 한다면 1000원짜리 동전 4개가 사용된다.
5. K를 (동전 액수 X 동전 개수)로 나눈 나머지로 위의 과정을 반복한다.
6. 마지막으로 count를 출력해준다.