d[11] = 1² + 2² + 3²
여기서 마지막항에 중점을 둬야하는데, 앞의 수들부터 “bottom-top”방식으로 식을 만들어 내려면, 앞의 수들의 구성에서 마지막으로 뭘 더하는지가 중요하기 떄문이다. d[11] 을 앞선 수들로 만들수 있는 조합은 3가지 경우인데,

• d[11] = d[11-1^] + 1² = d[10] + 1² = v1
• d[11] = d[11-2^] + 2² = d[7] + 2² = v2
• d[11] = d[11-3^] + 3² = d[2] + 3² = v3 이다.
  v1,v2,v3중 가장 작은 값으로 배열을 채워 나가면된다.

C++ 코드(bottom-top)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// bottom-up방식: 앞에 나온 경우들을 잘 이용해야함.

int arr[100001];

int main() {

	int n = 0;
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++)	 
		arr[i] = i;					//모두 1^2으로 채웠을때의 값으로 맞추기(최대의 개수)

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

	printf("%d", arr[n]);

}

C# 코드

using System.Text;
using System;
using static System.Console;

class Program
{
    static int[] arr = new int[100000];         //1부터 제곱수 들어갈 행렬
    public static void Main(string[] args)
    {
        int input = int.Parse(ReadLine());
        for(int i = 0; i<= input; i++)
        {
            arr[i] = i;
            for(int j = 0 ; j * j <= i; j++)
            {
                arr[i] = (arr[i] < (arr[i - j * j] + 1)) ? arr[i] : arr[i - j * j] + 1;
            }
        }
        Write(arr[input]);

    }
}

Java 코드

import java.util.*;

public class Main {
    static int[] arr = new int[100000];

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        int input = s.nextInt();

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

        System.out.println(arr[input]);
    }

}

Kotlin 코드

import java.util.*
import kotlin.math.*        // math 클래스의 min사용

fun main(args: Array<String>){
    val arr = IntArray(100000)

    val s = Scanner(System.`in`)
    val input = s.nextInt()

    for(i in 0..input){
        arr[i] = i
        var j = 0
        while(j*j<=i){
            arr[i] = min(arr[i], arr[i-j*j] + 1)
            j++
        }
    }
    print(arr[input])

}

Python 코드

x = int(input())

arr = [0 for _ in range(0, x+1)]

for i in range(0, x+1):
    arr[i] = i
    j = 0
    while j*j <= i:
        arr[i] = arr[i] if arr[i] < arr[i-j*j ]+1 else arr[i-j*j] +1
        j += 1

print(arr[x])