백준 1699번 : 제곱수의 합

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

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n;
    int[] dp;
    int min = 0;
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new int[n+1];
        dp[1] = 1;

        for(int i=2; i<=n; i++){
            min = 100000;
            for(int j=1; j<=i/2; j++){
                if(j*j==i){
                    min = 1;
                    break;
                }else{
                    min = Math.min(min, dp[j]+dp[i-j]);
                }
            }
            dp[i] = min;
        }

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



    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

자연수 n 의 최소 제곱수의 합은 자연수 n 이하의 제곱수들의 합으로 이루어진다.

자연수 n 까지 dp 배열에 자연수를 만들 수 있는 최솟값의 제곱수를 저장한다.

dp[1] = 1

dp[2] = 2

dp[3] = 제곱 수  일 경우 1 or dp[1]+dp[2] 값 중 최솟값을 저장

dp[4] = 제곱 수 일 경우 (2*2) 1 or dp[2] + dp[2] 값 중 최솟값을 저장

dp배열을 이러한 방식으로 초기화 한 이후에 주어진 자연수 dp[n]을 출력한다.