[BOJ] 백준 11047 동전 0 (Swift)

문제

https://www.acmicpc.net/problem/11047

11047번: 동전 0

풀이

그리디 알고리즘을 사용하여 풀이할 수 있습니다.

K가 0이 될 때 까지, K를 가장 큰 동전부터 나눈 몫을 더해주면 동전의 최소 개수를 구할 수 있습니다.

문제의 조건 중 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 라는 조건이 있기 때문에,
그리디 알고리즘이 성립하게 됩니다. 이러한 조건이 없다면 다른 방법을 사용하여 구현해야 될 것입니다.

동전의 가치는 오름차순으로 주어지기 때문에, 입력받은 후 뒤집어서 순회한다면 내림차순 순으로 조회할 수 있습니다.

소스코드

후기

조건을 보고 그리디 알고리즘이 성립한다는 것을 확인했다면 쉽게 풀 수 있는 문제입니다.