[Swift Algorithm] 동전 0 BOJ #11047

문제 설명

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

입출력 예

입력

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

출력

6

 

내 문제 풀이

import Foundation

let info = readLine()!.split(separator: " ").map({Int(String($0))!})
var money = [Int]()
var left = info[1]
var answer = 0

for _ in 0..<info[0] {
    let input = Int(readLine()!)!
    money.append(input)
}

while left > 0 {
    answer += left / money.last!
    left = left % money.removeLast()
}

print(answer)

이 문제는 그리디!

• 오름차순으로 입력되는 돈의 단위를 money 배열에 차례로 저장했다. (for문)
• info[1]로 입력된 돈 액수를 left 변수에 담아주었다. 연산을 반복하며 남은 액수를 담는 변수이다.
• while 문에서는 left 변수에 남은 돈이 0보다 클 때 반복하게 해줬고,
  결과를 담는 answer에, 남은 돈 left를 money 배열에서 가장 큰 액수(마지막 요소)로 나눈 결과를 더했다.
  그리고 남은 돈을 업데이트했는데, left를 money 배열에서 가장 큰 액수로 나눈 나머지를 저장했다.
  removeLast를 이용하여 반복마다 배열을 탐색할 필요 없이 마지막 요소로 계산하면 되도록하여 효율성을 높였다.

 

💡 피드백

• 어려운 문제는 아니라 금방 풀 수 있었다.
• 최적의 탐색 방법을 금방 찾을 줄 아는 것이 중요한듯하다.

 

---

 

문제

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