알고리즘
백준 - 동전0
koyuchang
2021. 2. 13. 13:59
문제 출처: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랑 나눴을 때 몫이 0보다 크면, 몫을 계속 ans변수에 더해줬다.
그리고 K는 나머지로 바꿔주면서 쭉 진행하면 정답이 나온다.