반응형
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
문제 설명
N종류의 동전으로 K원을 만들 때, 동전 개수의 최솟값을 구하는 문제이다.
풀이 과정
먼저 coin 리스트에 코인들을 오름차순으로 입력받게 되는데, 가장 적은 수의 코인을 갖기 위해서는 단위가 큰 코인부터 채워야 한다. 따라서 coin을 내림차순 정렬해주고 하나씩 차례대로 계산을 해주면 된다.
K원을 현재 코인으로 나눈 값의 몫을 누적해서 개수로 추가해주고 나머지는 다음 계산을 위해 저장한다.
n, k = map(int, input().split())
coin = []
for i in range(n):
coin.append(int(input()))
coin.sort(reverse=True)
count = 0
wallet = 0
for i in coin:
count += k // i
k = k % i
print(count)
전체 문제 & 코드는 위의 깃에 정리되어 있습니다.
팔로우 & 맞팔은 환영입니다 !
반응형
'Algorithm > Greedy' 카테고리의 다른 글
[백준] 2217 로프 (Python 파이썬) (0) | 2021.04.09 |
---|---|
[백준] 13305 주유소 (Python 파이썬) (0) | 2021.04.08 |
[백준] 1541 잃어버린 괄호 (Python 파이썬) (0) | 2021.04.08 |
[백준] 11399 ATM (Python 파이썬) (0) | 2021.04.08 |
[백준] 1931 회의실 배정 (Python 파이썬) (0) | 2021.04.08 |