[그리디] 백준 실버4 11047번: 동전 0(Swift)

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

11047번: 동전 0

Code

let NK = readLine()!.split(separator: " ").map { Int($0)! }

let N = NK[0]
var K = NK[1]
var coins: [Int] = []
var result = 0

for _ in 0..<N {
  let coin = Int(readLine()!)!
  if coin > K { break }
  coins.append(coin)
}

for i in 0..<coins.count {
  let coin = coins[coins.count - (1 + i)]
  let count = K / coin
  result += count
  K -= count * coin
}

print(result)

풀이과정

먼저 문제를 정리해 보자면,

첫 줄엔 동전의 종류와 동전으로 조합해야 할 K 값이 주어진다.

주어진 동전의 수는 무한대이며, 주어진 동전으로 K를 만드는데 필요한 동전의 최솟값을 출력하면 된다.

쉽게 접근하면, 최솟값이기 위해선 사용할 수 있는 동전 중 가장 큰 동전을 많이 사용하면 된다.

때문에 동전의 종류를 관리할 배열이 필요하다.

여기서 K보다 큰 동전은 사용할 일이 없음으로 K보다 작은 동전까지만 배열에 담는다.

그리고 반복문을 통해 배열의 가장 큰 동전부터 사용하여 K를 만들면 문제를 해결할 수 있다.