[BOJ] 11047번 동전 0

개요

가지고 있는 동전을 최소한으로 사용해 K원을 만드는 그리디 알고리즘 문제

요즘 코틀린 공부를 하고 있어서 코틀린으로 풀어보았다.

문제링크

코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var st = StringTokenizer(br.readLine())

    val n = st.nextToken().toInt()
    val k = st.nextToken().toInt()
    var coin = IntArray(n)
    repeat(n) {
        coin[it] = br.readLine().toInt()
    }

    var value = k
    var count = 0
    for (i in n-1 downTo 0) {
        if (value == 0)
            break
        if (value < coin[i])
            continue

        val quotient = value / coin[i]  //몫
        value %= coin[i]
        count += quotient
    }
    bw.use {
        it.write("$count\n")
    }
}

해결 과정

보통 이런 동전문제는 가장 높은 가치의 동전부터 최대한 사용하는 알고리즘을 떠올리기 쉬운데 이 알고리즘은 반례가 있는 경우가 많다. 그래서 다른 알고리즘을 생각해야 한다.

하지만 이 문제의 경우 문제조건에서 i>=2인경우 i번째 동전은 i-1번째 동전의 배수라는 특수한 조건이 붙으므로 큰 동전부터 최대한 사용하는 알고리즘 사용이 가능했다.

코틀린에 익숙해지기 위해 선택한 그리디문제였는데

다음번에는 위의 조건이 없는 동전문제를 풀어봐야겠다.

결과