[Java] BOJ 1699 제곱수의 합

1699번: 제곱수의 합

---

반례

753

# Answer
3 (625 + 64 + 64 = 753)

---

정답 코드

• 제곱수는 1로 설정하기
• 구하는 수는 범위내 dp[N-제곱수] + 1 중 가장 작은 값

import java.io.*;

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;
        
        for (int i = 2; i <= N; i++) {
            if (isPow(i)) {
                dp[i] = 1;
            } else {
                dp[i] = getMin(dp, i);
            }
        }

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

    private static int getMin(int[] dp, int index) {
        int min = Integer.MAX_VALUE;
        for (int i = 1; i * i <= index; i++) {
            min = Math.min(min, dp[index - i * i] + 1);
        }
        return min;
    }

    private static boolean isPow(int i) {
        return i % Math.sqrt(i) == 0 && (double) i / (double) Math.sqrt(i) == Math.sqrt(i);
    }
}