(JAVA) 백준온라인 1699번 - 제곱수의 합

dp배열에 n 까지의 모든 배열에 모두 1의 제곱으로 초기화 시킨다.

해당 i 안에서 j가 증가하며 기존 dp[i]와 새로 계산한 dp[i - j*j] + 1 중 최솟값을 해당 dp[i]에 저장한다

import java.util.Scanner;

public class Main {

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

        int n = sc.nextInt();
        int[] dp = new int[100001];

        for(int i = 0; i<=n; i++){
            dp[i] = i;
        }

        for(int i = 1; i<= n; 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]);
    }
}