백준 - 거스름돈(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/14916

 

[문제 설명]

2원짜리 동전과 5원짜리 동전으로 n원을 만들려고 한다.

가장 적은 동전 개수로 n원을 만드시오.

 

[접근 방법]

개인적으로 제일 어려워하는 동적프로그래밍 문제.

실버5인데도 사실상 야메로 풀었다. 사실 시간초과가 나야 하는 게 맞는데 Kotlin으로 풀어서 시간을 넉넉하게 통과시켜줬습니다.

모범 답안은 a원을 구할 때, a-2원 동전개수 + 1과 a-5원 동전개수 + 1 중에서 작은 값을 이용하는 것입니다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val dp = IntArray(n+11){Int.MAX_VALUE}
    dp[2] = 1
    dp[5] = 1

    for (idxOfDP in 3..n) {
        if (idxOfDP-2 > 0 && dp[idxOfDP-2] != Int.MAX_VALUE) {
            dp[idxOfDP] = dp[idxOfDP-2]+1
        }
        if (idxOfDP-5 > 0 && dp[idxOfDP-5] != Int.MAX_VALUE) {
            dp[idxOfDP] = dp[idxOfDP].coerceAtMost(dp[idxOfDP-5]+1)
        }
    }

    if (dp[n] != Int.MAX_VALUE) println(dp[n])
    else println(-1)
}

 

동적프로그래밍 조금씩 손 대고 있지만, 그리디와 같이 아이디어가 제일 중요한 문제 같습니다.

엄청 많이 풀어봐야겠습니다.