[백준][1699번] 제곱수의 합

문제 URL

https://www.acmicpc.net/problem/1699

나의 풀이

package backjoon;

import java.io.*;

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[] d = new int[n + 1];

        for (int i = 1; i <= n; i++)
            d[i] = Integer.MAX_VALUE;
            //d[i] = i; 했어도 됐다. 왜냐면 i를 넘을수없다. 1을 i번한게 최대니깐.

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                int sum = d[i - j * j] + 1;
                if (d[i] > sum)
                    d[i] = sum;
            }
        }

        System.out.println(d[n]);
    }
}

느낀점

동적계획법 을 이용한 문제다.

• d[i] = i를 제곱수의 합으로 나타냈을 때, 필요한 항의 최소개수 d[i] = min(d[n-ii]) + 1 (1 <= ii <= N)

• 시간복잡도 O(N*루트N)