[Algorithm] [Python&Swift] 백준/BOJ - 11047 _ 동전 0

11047 - 동전 0

 

문제

---

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

제출 코드

---

Python

n, k = map(int, input().split())
count = 0 
money = [int(input()) for _ in range(n)]
for i in range(n-1, -1, -1):
    if k >= money[i]:
        count += (k // money[i])
        k %= money[i]
    if k == 0:
        print(count)
        break

 

Swift

let line = readLine()!.split(separator: " ").map { Int($0)! }
let n = line[0]
var k = line[1]
var money = [Int]()
var result = 0
for _ in 0..<n {
    money.append(Int(readLine()!)!)
}
for i in stride(from: n-1, to: -1, by: -1) {
    if k >= money[i] {
        result += (k/money[i])
        k %= money[i]
    }
    if k == 0 {
        print(result)
        break
    }
}

 

문제풀이

---

문제는 주어진 동전을 적절히 활용하여 그 가치의 합을 K로 만들되, 필요한 동전의 개수를 최소화 해야한다.

최소한의 동전 개수로 이를 맞춰내기 위해서는 최대한 큰 금액의 동전을 최대한 많이 써야한다.

동전이 오름차순으로 입력되니 맨 마지막 값이 가장 큰 금액이 위치하게 된다.

따라서, 동전을 맨 뒤에서부터 앞 방향으로 순회하며 현재 동전값이 만들고자 하는 k 값 보다 작다면 이를 최대한 사용하는 방식을 이용하여 최소한의 동전 개수로 가치의 합을 만들어낸다.