백준 - 동전 0 (11047)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
var (N, K) = (input[0], input[1])
var coin = [Int]()
var answer = 0

for _ in 0..<N {
    coin.append(Int(readLine()!)!)
}

for value in coin.reversed() {
    if value <= K {
        answer += K / value
        K = K % value
    }
}

print(answer)

• 뒤의 동전 가격 Ai가 앞에 나오는 동전 가격 Ai-1의 배수 → 그리디 알고리즘을 사용할 수 있다
• 가격이 큰 동전부터 내림차순으로 탐색한다.
  • K보다 가격이 작은 동전이 나오는 경우
    • 사용 가능한 동전 개수는 K를 동전 가격으로 나눈 몫
    • 남은 K값은 K를 동전 가격으로 나눈 나머지