[백준] 11047번 동전 0 [Swift]

문제 링크

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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

문제 풀이

전형적인 그리디 알고리즘 문제인것 같다.

최소한의 동전으로 원하는 값을 만들기 위해서는 큰 동전부터 고려하면 된다.

이 문제에서는 처음 동전의 가치를 입력받을 때 값이 작은 동전부터 입력받기 때문에 정렬을 다시 해주는 과정이 필요할 것 같다.

 

값이 큰 동전부터 고려하는 예를 보며 이해해보자면

예를 들어 4200원을 최소한의 동전으로 나타내고 싶다면 5000원짜리 동전으로는 되지 않기 때문에 1000원 부터 시작하면 된다.

4200원은 1000원짜리 동전 4개가 있다면 200원이 남게된다.

200원은 가지고 있는 동전 중 100원으로 나타낼 수 있고 2개가 있으면 되므로 총 필요한 동전의 수는 6개가 된다.

 

소스 코드

func solution() -> Int {
    
    let temp = readLine()!.split(separator: " ").map({Int($0)!})
    let n = temp[0]
    var k = temp[1]
    
    var coins = [Int]()
    var result: Int = 0
    
    for _ in 0..<n{
        coins.append(Int(readLine()!)!)
    }
    
    coins = Array(coins.reversed())
    
    for value in coins{
        if value <= k{
            result += (k / value)
            k = (k % value)
        }
        if k == 0{
            break
        }
    }
    
    return result
}

print(solution())