[백준] 11047번: 동전 0 - Kotlin[코틀린]

문제

 

11047번: 동전 0

 

---

풀이

 

 이 문제는 그리디 알고리즘을 사용하여 해결하는 문제다. 그리디 알고리즘이란 현재 상황에서 최선의 선택을 고르며 해답을 찾는 알고리즘이다.

 

 유의할 점은 그리디 알고리즘은 항상 최적해를 보장하는 것이 아니라는 것이다. 예를 들어 어떤 경로 이동에서 매 순간 최적을 따라가면 1 - 1 - 1 - 100 순서로 이동하지만, 1 - 1 - 10 - 10 으로 움직이는 방법이 있을 수 있기 때문이다.

 

 따라서 어떤 문제에서 그리디 알고리즘을 적용하려면 필요한 문제의 속성들이 있다. 탐욕 선택 속성과 최적 부분 구조이다.

 

 - 탐욕 선택 속성: 선택의 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우

 - 최적 부분 구조: 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우

 

 그리디 알고리즘은 선택 절차, 적절성 검사, 해답 검사라는 3단계의 절차로 구성된다.

 

 1. 선택 절차: 현재 상태에서 최적인 선택을 한다.

 2. 적절성 검사: 선택한 항목이 문제의 조건을 만족시키는지 확인한다. 만족시키지 않으면 제외한다.

 3. 해답 검사: 선택이 완료되면, 최종 선택이 문제의 조건을 만족시키는지 확인한다. 조건을 만족시키면 해답으로 인정한다.

 

 그리디 알고리즘을 사용할 수 있는 대표적인 문제로 거스름돈을 구하는 문제가 있다. 거스름돈을 줄 때, 최대한 작은 수의 동전으로 주는 방법을 구하는 것인데 이번 동전 0 문제도 방법이 같다. 동전은 일반적으로 배수 관계이기 때문에 큰 동전부터 선택하면 가장 작은 개수의 동전을 사용하여 거스름돈을 줄 수 있다.

 

 이 문제의 풀이를 위의 3단계에 따라 설명하면 다음과 같다.

 

 1. 선택 절차: 가장 가치가 큰 동전부터 선택한다.

 2. 적절성 검사: 만약 선택한 동전의 가치가 거스름돈보다 크다면 해당 동전은 사용할 수 없으므로 다음 동전을 선택한다.

 3. 해답 검사: 동전의 합이 일치하면 문제가 해결된다.

 

 동전의 가치는 오름차순으로 입력되기 때문에 입력을 역순으로 확인해가며 필요한 돈보다 동전의 가치가 작다면 동전을 선택하고 개수를 세어주면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    var (num, money) = br.readLine().split(' ').map { it.toInt() }
    val coins = IntArray(num){ br.readLine().toInt() }

    var cnt = 0
    for(i in num - 1 downTo 0) {
        if(coins[i]<=money) { // 동전의 가치가 돈보다 작을 때
            cnt += money/coins[i]
            money %= coins[i]
        }
        if(money==0) break
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}