[백준-1699번/Java] 제곱수의 합

* DP ; 동적 계획법

* 1부터 N 범위까지 

- case1 : 가장 큰 제곱수 부터 빼는 연산, 전체 연산 횟수를 count에 저장

- case2 : 1 <= j < (i 의 제곱근) 범위의 의 dp[i - (j * j)] + 1해서 case1보다 작은 값이 있다면 저장

* 가장 큰 제곱수 부터 빼는 방식으로 해결 안됨.

반례) 753

3 (625 + 64 + 64 = 753)

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

public class Main {

	static private int largestSquareRoot(int num) {
		return (int) Math.sqrt(num);
	}

	public static void main(String[] args) throws IOException {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		int[] dp = new int[N + 1];

		for (int i = 1; i < dp.length; i++) {
			int count = 0;
			int num = i;
			while (num > 0) {
				num -= Math.pow(largestSquareRoot(num), 2);
				count++;
			}
			for (int j = 1; j < largestSquareRoot(i); j++) {
				count = Math.min(dp[i - (int) Math.pow(j, 2)] + 1, count);
			}
			dp[i] = count;
		}

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

}