[백준] 그리디 - 11047번 동전 0

11047번: 동전 0

입력 & 출력

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

풀이

K원을 동전 값으로 나누었을 때 몫이 0 이상인 경우를 구한다.
이 중 가장 적은 몫을 구해 k원에서 값을 빼준다.
이 과정을 K가 0이 될 때까지 반복한다.

 

Swift 전체 코드

let input = readLine()!.split(separator: " ")
var k = Int(input.last!)!
var coins : [Int] = []
var count = 0

for _ in 0..<Int(input.first!)! {
    coins.append(Int(readLine()!)!)
}

while k != 0 {
    let a = k / coins.last!
    if a > 0 {
        count += a
        k -= a * coins.last!
    }
    coins.removeLast()
}
print(count)