[Python] 백준/BOJ - 11047번: 동전 0

11047번: 동전 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

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 = []

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

cnt = 0

for i in range(n-1, -1, -1):
    if k < coins[i]:
        continue
    cnt += k // coins[i]
    k %= coins[i]
print(cnt)

 

먼저 n과 k를 입력받고, coins라는 빈 리스트를 만든다. for문을 n만큼 돌면서 input을 받아 coins배열에 동전 종류들을 입력받는다.

 

동전들은 오름차순으로 입력되었기 때문에 반복문을 n-1부터 거꾸로 돌아서 가장 큰 단위의 동전부터 확인해준다. 동전이 동전의 합 k 보다 큰 경우는 continue를 해서 다음 단위의 동전으로 넘어가주고, 그렇지 않은 경우에는 다른 문제들과 똑같이 풀어주면 된다.

 

맞았습니다!