알고리즘 문제(Swift) - 백준 - 11046 (동전 0)

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

 

 

 

여러 단위의 동전을 최소한 사용하여 목표 값을 만드는 문제

큰 단위의 동전부터 차례로 최대한 많이 사용하면 최소한의 동전으로 목표값을 만들 수 있음

→ 그리디 알고리즘

첫 번째 시도

let NK = readLine()!.split(separator: " ").map{Int($0)!}
let (N, K) = (NK[0], NK[1]) // N: 동전의 종류 개수, K: 목표 값
var coins = [Int]() // 동전 단위 배열
var target = K // 남은 값
var answer = 0 // 필요한 동전 개수
for _ in 0..<N {
    let coin = Int(readLine()!)!
    if coin <= K { // 동전 단위 중 목표값(K)보다 작은 코인만 추가
        coins.append(coin)
    }
}

for coin in coins.reversed() { // 단위가 가장 큰 코인부터 확인 (최선의 선택)
    answer += target / coin      // 코인으로 나눈 몫 (코인 개수)의 합
    target %= coin              // 남은 값 수정
    if target == 0 { break }    // 남은 값이 없으면 break
}

print(answer)