BOJ 1699. 제곱수의 합

BOJ 1699. 제곱수의 합

풀이

d[i] = i을 제곱수의 합으로 나타낼 수 있는 최소 항의 개수

마지막으로 올 수 있는 수들은 11, 22, 33….. jj이다.
즉 , O+O+O+O+…. (j*j) = i 으로 표현된다.

(i - jj) + (jj) = i로 표현할 수 있고, 마지막  j*j는 한 가지 방법이므로 +1이다.
(i - j*j) + 1 이다.

점화식
d[i] = min(d[i - jj ]) +1 즉, d[i] = min(d[i], d[i - jj] +1)
1 <= j <= i

import java.io.IOException;
import java.util.Scanner;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n + 1]; // 최소항의 개수

        for (int i = 1; i <= n; i++) {
            d[i] = i;
            for (int j = 1; j * j <= i; j++) {
                d[i] = Math.min(d[i], d[i - j * j] + 1);
            }
        }

        System.out.println(d[n]);
    }
}

import kotlin.math.min

fun main() {
    val n = readLine()!!.toInt()
    val d = IntArray(n + 1)

    for (i in 1..n) {
        d[i] = i
        var j = 1
        while (j * j <= i) {
            d[i] = min(d[i], d[i - j * j] + 1)
            j++
        }
    }
    println(d[n])
}

풀이소스

github.com/beomjo/algorithm-study/commit/84ff043e04486adc457340873afd4aac6e3aa44c