동전의 종류가 주어진다.
최소 동전의 개수로 주어진 수를 완성해야한다.
가장 큰 동전부터 주어진 수 K에서 빼본다.
만약 결과가 음수라면, 다음 작은 동전 값을 뺀다.
K에서 동전값을 빼서 0보다 같거나 큰수이면 K에서 동전값을 나누고, 나머지를 K에 저장해서 다시 반복한다.
for i in range(N- 1, -1, -1):
if K - coin[i] >= 0:
cnt += K // coin[i]
K %= coin[i]
for
: O(n)O(n)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
난이도 | 정답률(%) |
---|---|
실버2 | 52.492% |