코딩 테스트 - [백준 11047: 동전] (탐욕 알고리즘)

문제

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

 

예제 입력

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력

6

 

나의 답안:

var coinArr = [Int]()
var num = readLine()!.components(separatedBy: " ").map{Int(String($0))!}
var k = num[1]
var count = 0

for i in 0..<num[0] {
    var coin = Int(readLine()!)!
    coinArr.append(coin)
}

for j in stride(from: num[0]-1, through: 0, by: -1) {
    if k == 0 {
        break
    }
    if k / coinArr[j] == 0 {
        continue
    } else if k / coinArr[j] != 0 && k/coinArr[j] > 0 {
        count += k/coinArr[j]
        k = k % coinArr[j]
    }
}

print(count)

 

문제 설명:

가치의 합을 큰 동전에서 작은 순으로 나누어 간다. (탐욕 알고리즘 사용)

예로 5 , 4720을 입력한 후, 가지고 있는 동전을 10 100 1000 10000 50000 이라고 가정한다.

1. 4720을 가장 큰 동전인 50000으로 나눈다. 나눠지지 않으므로 나눈값은 0이다.

2. 4720을 다음으로 큰 동전인 10000으로 나눈다. 마찬가지로 나눠지지 않으므로 나눈값은 0이다.

3. 4720을 다음으로 큰 동전인 1000으로 나눈다. 4720/1000 = 4이므로 count가 4가된다. 가치의 합은 4720을 1000으로 나눈 나머지인 720이 된다.

4. 720을 다음으로 큰 동전인 100으로 나눈다. 720/100 = 7 이므로 count는 4+7인 11이 된다. 가치의 합은 720을 100으로 나눈 나머지 값인 20이 된다.

5. 20을 다음으로 큰 동전인 10으로 나눈다. 20/10 = 2 이므로 count는 11+2인 13이 된다. 가치의 합은 0이 된다.

6. 반복문이 종료되고 count 값인 13이 출력된다.