[백준] 17626번 Four Squares (silver 3

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int n=Integer.valueOf(br.readLine());
        int[] num=new int[n+1];
        num[0]=10000;
        for(int i=1; i<=Math.sqrt(n)+1; i++){
            if(i*i<=n){
                num[i*i]=1;
            }
        }

        for(int i=1; i<=n; i++){
            if(num[i]==1){
                continue;
            }
            int min=Integer.MAX_VALUE;
            for(int j=1; j<=Math.sqrt(i); j++){
                int temp=num[j*j]+num[i-j*j];
                min=Math.min(min, temp);
            }
            num[i]=min;
        }


        bw.write(num[n]+"");
        bw.flush();
        
    }
}

// 해당 문제는 제곱수의 합으로 수들을 표현하는 것이다.
// 부분의 최적은 결국 전체의 최적이 적용된다. 왜냐하면, 결국 수가 커지는 건 밑에 작은 수의
// 방법 +a 방식이기 때문이다. 따라서, 완전제곱수로 1가지의 수로 표현되는 방식들을 초기화 한 뒤,
// 이를 제외한 수들의 방법 수를 점차 정하는 방법으로 해결했다.