문제
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
풀이
문제를 보자마자 전형적인 그리디 유형이라는 생각이들었다.
그렇기 때문에 가장 높은 화폐부터 나누어가면 된다고 생각했다.
우선 배열로 동전값을 받은 후 sort를 통해 가장 높은 동전으로 정렬을 수행한다.
이후 높은 화폐부터 나누어 가고 몫은 동전 개수에, 나머지는 다음 동전으로 연산을 해나간다.
추가로 나누기 전에 화폐가 k보다 클 경우에는 의미가 없으므로 조건문을 하나 추가했다.
n, k = map(int, input().split())
coins = []
for _ in range(n):
coins.append(int(input()))
# 높은 동전 순으로 정렬
coins.sort(reverse=True)
result = 0
for coin in coins:
if k == 0:
break
if k >= coin:
count, remain = divmod(k, coin)
# 몫은 개수에, 나머지 값은 본래 k값에 할당
result += count
k = remain
print(result)
'Algorithm > Problem Solving' 카테고리의 다른 글
[Beakjoon] 1026 : 보물 - python (0) | 2025.01.24 |
---|---|
[Beakjoon] 1343 : 폴리오미노 - python (0) | 2025.01.24 |
[Baekjoon] 2839 : 설탕 배달 - python (1) | 2025.01.23 |
[이코테] 1이 될 때까지 - python (0) | 2025.01.23 |
[이코테] 숫자 카드 게임 - python (0) | 2025.01.23 |