[백준/파이썬] 11047번 동전 0

동전 0

• 15단계 그리디 알고리즘 - 1단계
• 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 $A_{i}$가 오름차순으로 주어진다. (1 ≤ $A_{i}$ ≤ 1,000,000, $A_{1}$ = 1, i ≥ 2인 경우에 $A_{i}$는 $A_{i-1}$의 배수)

 

 

출력

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

 

 

예제 입력 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 1

6

 

 

예제 입력 2

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 2

12

 

제출 코드

n, k = map(int, input().split())
coins = []
cnt = 0
for _ in range(n):
    coins.append(int(input()))

coins.sort(reverse=True)

for i in coins:
    if i <= k:
        cnt += (k // i)
        k %= i
    if k == 0:
        break

print(cnt)

 

그리디 알고리즘을 통해 풀었다.

 

1. 즉, 가장 동전을 값이 가장 큰 순으로 coins라는 리스트에 정렬한다.

2. 큰 수부터 차례로 값 k에 대입하여 k보다 작으면 해당 수로 나누고 그 몫이 바로 쓰인 동전의 개수이므로 cnt라는 변수에 넣어주어 동전의 개수를 센다

3. 동전을 쓴만큼 k값에서 빼주어야하기 때문에 나눈 후의 나머지 값으로 k를 대체한다.

4. 만약 계산 후 k값이 0이라면 최소의 동전 개수로 k값을 완성하는 데에 성공한 것이므로 break를 만나 for문을 빠져나온다.