백준 - 14916 거스름돈 (코틀린)

[문제]

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

14916번: 거스름돈

[풀이]

n이 5의 배수이면 5로 나눈 몫을 반환하고 그렇지 않으면 2를 빼준다. 다시 5의 배수인지 확인하고 그렇지 않으면 2를 뺴준다.

5의 배수인지 확인하고 맞으면 우선적으로 5로 나눠주는 작업을 하기 때문에 그리디알고리즘으로 푼다고 볼 수 있다.

시간복잡도 : O(N)

[코드]

private var n = 0
private var result = 0
fun main() {
    val br = System.`in`.bufferedReader()
    n = br.readLine().toInt()
    while(n > 0 ){
        if(n%5 == 0){
            result += n /5
            break
        }
        else {
            n -= 2
            result += 1
        }
    }
    println(if(n>=0) result else -1)
}