[백준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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

📝 풀이

import sys
n, k = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
  inp = int(sys.stdin.readline())
  if inp <= k:
    arr.append(inp)

arr.sort(reverse=True)
answer = 0
for i in arr:
  answer += k//i
  k = k%i

print(answer)

 

그리디의 대표적인 문제인 동전 개수 문제였다.

이 문제의 해결법은 가장 큰 화폐 단위부터 동전 개수를 세는 것이다.

 

먼저 n과 k에 동전의 개수와 원하는 금액을 저장했다.

그리고 for문을 돌며 inp에 입력받은 동전의 금액을 임시로 저장하고 이 동전의 값이 k보다 작거나 같을 때만 arr에 넣어주었다.

왜냐하면 해당 동전이 원하는 금액보다 크면 그 금액을 만들 수 없기 때문이다.

 

for문이 끝나면 arr에는 k보다 작은 값을 가진 동전들이 오름차순으로 들어있다.

이를 .sort() 메서드를 사용해 내림차순으로 바꿔주고 다시 for문으로 arr을 순회한다.

 

i는 제일 큰 값의 동전부터 들어가기 때문에 k를 i로 나눈 몫을 answer에 더한다.

이후 k는 k를 i로 나눈 나머지의 값으로 갱신한다.

 

예를 들어 arr = [ 1000, 500, 100 ], k = 2600이면 이 과정은 다음과 같이 나타낼 수 있다.

 

k	i	k // i	k % i
2600	1000	2	600
600	500	1	100
100	100	1	0

 

따라서 이 경우 동전의 개수는 2+1+1 = 4 가 된다.

 

마지막으로 for문의 순회가 끝났다면 동전 개수가 담긴 answer를 출력한다.