이번에 풀어본 문제는
백준 1699번 제곱수의 합 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 모든 수는 일단 1의 제곱을 나열하여 표현 가능
            for (int j = 1; j * j <= i; j++) {
                // i - (제곱수 + 1)이 가능한 모든 경우의 수 중 최솟값 탐색
                int tmp = dp[i - (j * j)];
                if (dp[i] > tmp + 1) dp[i] = tmp + 1;
            }
        }
        System.out.print(dp[n]);
    }
}

📝 풀이

n이 주어졌을 때, n을 제곱수만을 사용하여 만들 수 있는 최소 개수를 출력하는 문제입니다.
n을 제곱수로 만들 수 있는 모든 경우의 수는
1. 1의 제곱만 사용
2. n - (i * i)의 경우의 수 + 1의 제곱
두 가지로 나눠질 수 있습니다.

위를 반복문으로 구현하여 풀어보았습니다.