문제링크 : https://www.acmicpc.net/problem/11047
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
작성코드
해설
조건으로 동전은 배수로서 주어진다는 것을 알게 되었으니 문제가 간단해진다.
동전 사용 갯수를 최소로 만들기 위해서는 큰 동전을 최대한 많이 사용하면 되므로
해당 금액에서 사용할 수 있는 가장 큰 동전을 사용하고 남은 금액을 다시 반복해주면 된다.
이를 코드로 작성하면 아래와 같다.
동전 입력은 오름차순으로 주워지므로 역순으로 가장 큰 동전부터 계산해준다.
현재 금액 K 보다 동전이 클 경우 넘겨주고
동전이 작을 경우 K 금액을 동전 I로 나눠 몫만큼 카운트하고 K를 줄여준다.
이를 계속 반복해준다.
'백준 > Python' 카테고리의 다른 글
| [백준] 11399 ATM (python 파이썬) (0) | 2023.01.11 |
|---|---|
| [백준] 1931 회의실 배정 (python 파이썬) (0) | 2023.01.10 |
| [백준] 11660 구간 합 구하기 5 (python 파이썬) (0) | 2023.01.02 |
| [백준] 26217 별꽃의 세레나데(Easy) (python 파이썬) (0) | 2022.12.22 |
| [백준] 26215 눈 치우기 (python 파이썬) (0) | 2022.12.22 |