kingsubin

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

public class boj_1699 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static long[] dp;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        dp = new long[n+1];

        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 최솟값을 i로 초기화 , i를 넘을 수 없음
            for (int j = 1; j*j <= i; j++) {
                if (dp[i] > dp[i-j*j] + 1) {
                    dp[i] = dp[i-j*j] + 1;
                }
            }
        }

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

 

- n을 만드는 과정에서 마지막에 올 수 있는 수는 1^2, 2^2, ... 이 있다. -> 변수로 생각 i

- 그렇다면 나머지는 n-i^2 이고 dp[n] = dp[n-i^2] + 1로 볼 수 있다.

- 여기서 i^2의 범위는 1 ~ n까지이고 반복하며 최솟값을 dp에 넣어준다.

- dp의 초기값은 현재값을 넣어준다. 1^2 끼리만 더하는게 최대값이다.