[백준 - 7490] 0 만들기

문제링크

첫번째 시도 (실패)

• 가장 큰 제곱수를 기준으로 dp값을 계산하면 해결될 줄 알았지만 예외 케이스가 있는거 같은데 아직 발견은 못했습니다...

import kotlin.math.pow
import kotlin.math.sqrt

fun main() {
    val bufferedReader = System.`in`.bufferedReader()
    val bufferedWriter = System.out.bufferedWriter()

    val n = bufferedReader.readLine().toInt()
    val squares = getSquares(n.toDouble())
    val dp = Array(n + 1) { 0 }
    dp[1] = 1

    var biggestSquare = 1
    for (i in 2..n) {
        if (i in squares) {
            dp[i] = 1
            biggestSquare = i
        } else {
            dp[i] = dp[biggestSquare] + dp[i - biggestSquare]
        }
    }
    bufferedWriter.write("${dp[n]}")

    bufferedReader.close()
    bufferedWriter.close()
}

fun getSquares(n: Double): List<Int> {
    val squares = mutableListOf<Int>()
    for (i in 1..sqrt(n).toInt()) {
        squares.add(i.toDouble().pow(2).toInt())
    }
    return squares
}

두번째 시도 (성공)

• 현재 찾고자 하는 dp값보다 작은 제곱수 모두 검사합니다.

import kotlin.math.min

fun main() {
    val bufferedReader = System.`in`.bufferedReader()
    val bufferedWriter = System.out.bufferedWriter()

    val n = bufferedReader.readLine().toInt()
    val dp = Array(n + 1) { Int.MAX_VALUE }
    dp[0] = 0
    dp[1] = 1

    for (i in 2..n) {
        var j = 1
        while (i >= j * j) {
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j++
        }
    }
    bufferedWriter.write("${dp[n]}")

    bufferedReader.close()
    bufferedWriter.close()
}

주석 없는 코드를 만들기 위해 노력하는 개발자입니다.

혹시라도 의도가 분명하지 않아보이는 (이해가 되지 않는) 코드가 있으시다면 편하게 답변 달아주시면 정말 감사하겠습니다.