[백준 2720번] [Kotlin] 세탁소 사장 동혁

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

2720번: 세탁소 사장 동혁

 

난이도 : 브론즈 3
태그 : 수학, 그리디, 사칙연산

 

 

설명

줘야하는 동전의 개수가 최소가 되야하는 문제입니다.

그리디 알고리즘의 기초격인 문제인데요.

단순히, 현재 줘야하는 금액에서 25센트 짜리 동전을 최대한 거슬러 주고,

그 다음 10, 그 다음 5, 나머지 1센트 짜리 동전으로 거슬러 주면 됩니다.

 

 

 

소스코드

import java.lang.StringBuilder

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    val coin = intArrayOf(25, 10, 5, 1)

    repeat(readLine().toInt()) {
        var n = readLine().toInt()
        val cnt = arrayOf(0, 0, 0, 0)

        for (i in coin.indices) {
            cnt[i] = n / coin[i]
            n %= coin[i]
        }

        sb.append("${cnt[0]} ${cnt[1]} ${cnt[2]} ${cnt[3]}\n")
    }

    print(sb)
}

 

이를 코드로 표현하면 위와 같습니다.

매 번 n에서 25, 10, 5, 1센트를 빼는 방법도 있지만,

n/coin[i]를 사용하면 한 번에 거슬러 줄 수 있는 동전의 개수를 구할 수 있습니다.

 

123센트를 거슬러 줘야 한다면,

123 / 25 = 4 (소숫점 절삭)이므로, 25센트짜리 동전 4개를 사용해 나눠줄 수 있고,

123 % 25 = 23으로, 25센트 짜리 동전을 거슬러 주고 남은 금액을 알 수 있죠.

 

 

후기

그리디 알고리즘 입문 문제로써 꽤나 교육적인 문제인 것 같습니다.