목차
1. 문제
2. 입출력 예시
입력 예시 | 출력 예시 |
---|---|
10 4200 1 5 10 50 100 500 1000 5000 10000 50000 | 6 |
10 4790 1 5 10 50 100 500 1000 5000 10000 50000 | 12 |
3. 문제 풀이
이 문제 역시 굉장히 간단했다. 이를 해결하기 위한 순서는 다음과 같다.
- 동전 종류의 수량(
N
)과 가치의 합(K
)를 입력받는다. - 동전의 가치가 담긴 정보(
A
)를 입력받는다. - 동전의 가치는 오름차순으로 주어지므로, 이를 내림차순으로 정렬한다.
- 반복문을 통해 동전의 가치가 담긴 리스트를 반복하며, 가치의 합에 동전 가치를 나눈 몫을 동전 수량에 더해준다. 그리고 가치의 합은 가치의 합에 동전 가치를 나눈 나머지로 적용한다.
- 가치의 합을 맞추기 위한 동전의 수량을 출력한다.
이를 코드로 나타내면 아래와 같다.
def solution(k, a):
a.sort(reverse=True)
cnt = 0
for i in a:
cnt += k // i
k %= i
print(cnt)
N, K = [int(x) for x in input().split(" ")]
A = [int(input()) for x in range(N)]
solution(K, A)
위 코드의 메모리는 28,776 KB
, 시간은 84 ms
가 소요되었다.
'Algorithm > Baekjoon' 카테고리의 다른 글
Baekjoon #1541 - 잃어버린 괄호 (0) | 2021.03.22 |
---|---|
Baekjoon #5585 - 거스름돈 (0) | 2021.03.21 |
Baekjoon #1931 - 회의실 배정 (0) | 2021.03.21 |
Baekjoon #11399 - ATM (0) | 2021.03.20 |
Baekjoon #2839 - 설탕 배달 (0) | 2021.03.20 |