[백준/BOJ] 1699번: 제곱수의 합

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

1699번: 제곱수의 합

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

해설

문제를 간단히 말하면 자연수를 제곱수의 합으로 나타낼 때 항의 최소 개수를 출력하는 것이다.

우선 dp[i] = i로 하였다.

이는 1로만 i를 만들었을 때의 가장 많은 항을 가지는 수이기 때문이다.

 

이제 14를 예시로 들어보겠다.

14까지의 제곱수 중 가장 큰 수는 3이 될 것이다.

제곱수들만 보는 이유는 dp[1], dp[4], dp[9] 모두 1², 2², 3²으로 항의 개수가 1이기 때문이다.

 

따라서

dp[14-1], dp[14-4], dp[14-9]에서 가장 항이 적은 값에 +1을 하면 된다.

(1, 4, 9의 최소 항이 1이기 때문에 +1을 한다.)

 

이제 점화식을 알 수 있다.

dp[i] = min(dp[i], dp[i - j * j] + 1)

 

이 과정을 반복하여 dp[n]을 출력하면 된다.

소스 코드

import kotlin.math.min

fun main() = with(System.`in`.bufferedReader()){
    val n = readLine().toInt()
    val dp = Array(n+1) { i -> i }
    for(i in 1 .. n) {
        for(j in  1 .. i ) {
            if(j * j > i) break
            dp[i] = min(dp[i], dp[i- j * j] + 1)
        }
    }
    println(dp[n])
}