21.07.16 - [BOJ] 1699. 제곱수의 합

[suhyunsim]

문제

• 1699

핵심 아이디어

• D[N] = N을 제곱수의 합으로 나타낼 때의 항의 최소 개수
• D[i] = min(D[i - j^2] + 1) (1 <= i <= j^2)

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q1699;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            d[i] = i;
            for (int j = 1; j * j <= i; j++) {
                if (d[i] > d[i - j * j] + 1) {
                    d[i] = d[i - j * j] + 1;
                }
            }
        }
        System.out.println(d[n]);
    }
}