[백준 1699] 제곱수의 합 (JAVA)

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

1699번: 제곱수의 합

 

index보다 작은 제곱수의 최소합을 확인하여 구해나가면 된다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp=new int[n+1];
		for(int i=1;i<=n;i++) { //최댓값으로 세팅한다.
			dp[i]=i;
		}	
		for(int i=1;i<=n;i++) {
			for(int j=2;j*j<=i;j++) {
				if(dp[i]>dp[i-(j*j)]+1) { //i보다 작은 제곱값의 최소합을 확인!
					dp[i]=dp[i-(j*j)]+1;
				}
			}
		}

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

}