Four Squares(백준)

package com.dofury.kotlin

import kotlin.math.min

fun main() {
    val n = readLine()!!.toInt()
    val dp = IntArray(n + 1) { Int.MAX_VALUE }
    dp[0] = 0
    for (i in 1..n) {
        var j = 1
        while (j * j <= i) {
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
        }
    }
    println(dp[n])
}

문제를 안풀려 찾아보니 다이나믹 프로그래밍을 해야했다.

dp 인트배열을 최소값을 구해야하니 int에서 가장큰값으로 초기화한다.

그다음 1부터 n까지 반복해서

j의제곱이 i보다 같거나 작을때만 최소값을 대입하는 반복문을 돌린다.

dp[i]는 dp[i- j*j] + 1과 비교해서 더 작은 값을 가진다.

 

이를 이해하기위해서 예시를 들자면

11339 = 105^2 + 15^2 + 8^2 + 5^2 이므로 이 는

105^2 + 15^2 + 8^ 2 에서 + 1을 더한 갯수와 같다.

 

그래서 이 점을 이용해 비교해서 더작은 값을 대입하게 된다.

 

 

그다음  문제에서 요구하는 dp[n]을 출력한다.