[DP]문제#9.제곱수의 합(☆)

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

1699번: 제곱수의 합

import java.util.Scanner;

//제곱수의 합
public class Main {

	static int n;
	static int d[];
	public static void main(String[] args) {
		
		Scanner in=new Scanner(System.in);
		n=in.nextInt();	
		d=new int[n+1];
	
		d[1]=1;
		for(int i=2;i<=n;i++) {
			if(Math.pow(i, 2)<=n) d[(int) Math.pow(i, 2)]=1;
			if(d[i]==1) continue;
			d[i]=i;
			for(int j=1;j<=i/2;j++) {
				d[i]=Math.min(d[i], d[j]+d[i-j]);
			}
		}
		System.out.println(d[n]);	
	}
}