[ JAVA / 백준 : 1699 ] 제곱수의 합

풀이

N에 가장 가까운 제곱수를 뺀 dp값의 + 1이다!

dp[i] = Math.min(dp[i], dp[i - j * j] + 1)

---

import java.util.Scanner;

public class 제곱수의합 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();
		
		int[] dp = new int[100001];
		dp[0] = 0; dp[1] = 1;
		for(int i = 2; i <= N; i++) {
			dp[i] = i; //처음에 1의제곱으로만 표현할 수 있는 개수로 초기화
			for(int j = 1; j * j <= i; j++) {
				dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
			}
		}
		System.out.println(dp[N]);
		scan.close();
	}
}