(Java) 백준 17626 - Four Squares

처음에는 이 문제를 어떻게 풀어야 할지 전혀 감을 못 잡았다.

한참을 생각해도 답이 안 나와서 다른 분들 풀이를 참조했다.

DP를 이용하는 문제였는데, 점화식도 생각보다 복잡해서 이해하는데

한참 걸렸다. 코드 자체는 어렵지 않으나 dp[i] = min(dp[i - j * j]) + 1 이라는

점화식을 생각하는 부분이 가장 어려웠던 것 같다.

---

최종 코드

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

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

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

        int min = 0;
        for (int i = 2; i <= n; i++) {
            // 최솟값을 비교하기 위한 초기값
            min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                int temp = i - j * j;
                min = Math.min(min, dp[temp]);
            }
            dp[i] = min + 1;
        }
        System.out.println(dp[n]);
    }
}