Kotlin] 백준 2720번 문제풀이

https://www.acmicpc.net/problem/2720

2720번: 세탁소 사장 동혁

 

 

 

풀이

간단한 그리디 문제입니다.

그리디에 대한 설명은 요기.

https://itstudy-mary.tistory.com/448

탐욕 알고리즘(Greedy Algorithm)

 

그리디 문제 풀 듯, 가장 큰 수부터 나누어 몫 -> 거스름돈으로 나누어 저장하고, 몫으로 나눈 나머지로 좀 더 작은 동전으로 거슬러주면 됩니다. 거슬러준 동전은 리스트로 저장하고, 동전 배열을 다 돌았다면 리스트를 joinToString을 통해 문자열로 합쳐서 프린트 하면 됩니다.

진법 문제(2745번, 11005번) 풀이와 비슷하지만 좀 더 쉽습니다.

(진법 문제는 풀어놓았습니다)

fun main(args: Array<String>) {
    question2720()
}

fun question2720() {
    var case = readLine()!!.toInt()
    var coinArray = arrayOf(25, 10, 5, 1)

    for (i in 1 .. case ) {
        var money = readLine()!!.toInt()
        var moneyArray = mutableListOf<Int>()

        for(i in coinArray.indices) {
            moneyArray.add(money / coinArray[i])
            money %= coinArray[i]
        }

        println(moneyArray.joinToString(" "))
    }
}