[백준] 1699번 제곱수의 합

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

1699번: 제곱수의 합

 

dp[ 1 ]	1²			1
dp[ 2 ]	1² + 1²			2
dp[ 3 ]	1² + 1² + 1²			3
dp[ 4 ]	2²			1
dp[ 5 ]	2² + 1²	[5 - 2²] = 1	dp[1] + 1	2
dp[ 6 ]	2² + 1² + 1²	[6 - 2²] = 2	dp[2] + 1	3
dp[ 7 ]	2² + 1² + 1² + 1²	[7 - 2²] = 3	dp[3] + 1	4
dp[ 8 ]	2² + 2²	[8 - 2²] = 1	dp[4] + 1	2
dp[ 9 ]	3²			1
dp[ 10 ]	3² + 1²			2

 

점화식 : dp[i] = dp[i - j ²] + 1

 

 

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[100001];
        dp[1] = 1;
        for(int i = 2; i <= N; i++) {
            dp[i] = i;
            for(int j = 1; j * j <= i; j++) {
            	dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
            }
        }
        System.out.println(dp[N]);
    }
}