[백준 5585번] [Kotlin] 거스름돈

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

5585번: 거스름돈

 

난이도 : 브론즈 2
태그 : 그리디

 

 

설명

500엔, 100엔, 50엔, 10엔, 5엔, 1엔으로 잔돈을 거스름돈 하는 문제입니다.

전형적인 그리디 알고리즘 문제인데요.

가장 최적의 해를 연속하여 선택하는 방법입니다.

이 문제에서는 거스름돈의 개수가 가장 적어야 하므로,

단위가 가장 큰 500엔부터, 100, 50, 10, 5, 1엔 순으로 선택하면 되겠네요.

 

 

소스코드

fun main() {
    var n = 1000 - readln().toInt()
    val m = arrayOf(500, 100, 50, 10, 5, 1)
    var cnt = 0
    var idx = 0

    while (n > 0) {
        if (n >= m[idx]) {
            n -= m[idx]
            cnt++
        } else {
            idx++
        }
    }

    println(cnt)
}

 

 

코드 분석

1. 줘야 할 잔돈 n을 구한다 (문제에서, 항상 고정적으로 1000엔을 낸다 했으니, 1000 - 타로값 으로 구할 수 있다)
2. 잔돈을 셀 변수 cnt와, 현재 줘야 할 잔돈의 위치를 담을 idx를 생성한다.
3. while 문을 돌며 현재 잔돈으로 거슬러 줄 수 있으면, 줘야하는 돈에서 현재 금액 단위만큼 빼고, cnt를 1 증가시킨다.
4. 만약 현재 단위로 거슬러 줄 수 없으면 다음 단위로 가기 위해 idx를 +1 한다.
5. 잔돈이 0 보다 클 때까지 3~4를 반복한다.