[백준] 11047번 동전 0 해설 및 풀이 (Python)

백준 11047번 - 동전 0

https://www.acmicpc.net/problem/11047

---

문제

준규가 가지고 있는 동전은 총 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. N과 K를 주어지기 때문에 입력을 받는다. 동전의 가치는 오름차순으로 주어지고 항상 이전의 동전의 배수이다.
2. 출력은 첫째줄에서 입력한 K원을 만드는데 필요한 동전 개수의 최소값을 출력해야 한다.
3. 두번째 줄부터 N개의 동전의 값을 입력 받는다. 가장 큰 동전부터 사용해야 하기 때문에 우선, 입력 받은 동전의 리스트를 내림차순으로 정렬한다.
4. 큰 동전부터 K에 대해 나누어서 몇 개를 사용할 수 있는지 계산한다. (K // coin)
5. 사용한 동전 개수를 카운트 변수에 대입하고, 남은 금액을 업데이트 한다. ( K % coin)

 

시간 복잡도

 

N개의 동전을 한 번 순회하면서 나누기와 나머지 연산을 수행하기 때문에 시간복잡도는 O(N)

 

---

 

문제 풀이 코드

 

n, k = map(int, input().split()) # N, K 입력 받기
coins = [int(input()) for _ in range(n)] # 동전 리스트 입력 받기
coins.sort(reverse=True) # 정렬


count = 0 # 필요한 동전 개수
for coin in coins:
    count += k // coin  # 현재 동전으로 만들 수 있는 개수 추가
    k %= coin  # 남은 금액 업데이트
    if k == 0:  # 목표 금액을 만들었으면 종료
        break
print(count)