이번에 풀어본 문제는
백준 17626번 Four Squares 입니다.

📕 문제 링크

❗️코드

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];
        dp[0] = 0;
        dp[1] = 1;

        int min;
        for (int i = 2; i <= n; i++) {
            min = Integer.MAX_VALUE;

            for (int j = 1; j * j <= i; j++) {
                int tmp = i - (j * j);
                min = Math.min(min, dp[tmp]);
            }
            dp[i] = min + 1;
        }

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

📝 풀이

입력된 n을 제곱수들의 합으로 구성할 수 있는 최소 개수를 출력하는 문제입니다.
처음엔 무조건 n과 가장 가까운 제곱수와 그 나머지를 구하면 된다고 생각했는데,
12의 경우를 보시면 3의제곱인 9를 사용한 경우가 아니라 2의제곱 4를 3개 사용한 경우가 더 최소 경우의 수 입니다.
따라서 다른 경우도 고려해야했습니다.
모든 수는 제곱수로 구성되어있기 때문에
dp[n]의 결과는 n보다 작은 제곱수 + dp[나머지값]이 될 것입니다.
여기서 제곱수는 모두 1이므로 dp[나머지값]의 최소를 구해 + 1만 해주면 해결할 수 있습니다.
예를들어 n = 5일때,
제곱수로 1^2 , 2^2 가 선택될 수 있습니다.
1^2를 선택했을때는 1^2 + dp[4],
2^2를 선택했을때는 2^2 + dp[1]이 될 것입니다.
따라서 둘 중 작은 값인 dp[4]가 min이 되며, 결과는 2가 됩니다.