[백준]1699. 제곱수의 합 (Java)

💡 문제 분석

가능한 모든 제곱 수의 합을 구해보고, 가장 작은 수를 배열에 저장합니다

---

⌨️ 코드

JAVA

import java.util.Scanner;

public class Q1699 {
    static int[] cache;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        cache = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            cache[i] = i;
            for(int j = 1; j <= Math.sqrt(i); j++)
                cache[i] = Math.min(cache[i], cache[i - j * j] + 1);
        }

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

Uploaded by Notion2Tistory v1.1.0