[백준저지] 1699번 : 제곱수의 합

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

1. 제목

주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제.

 

입)

7

 

출)

4

 

2. 풀이

import java.util.*;

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++) {
                int L = D[i - j * j] + 1;
                if (D[i] > L) {
                    D[i] = L;
                }
            }
        }
        System.out.println(D[N]);
    }
}

D[i] -> i를 제곱수의 합으로 나타냈을 때, 필요한 항의 최소 개수

D[i] = min(D[i-j*j])+1, 1 <= j * j <= i

위 점화식을 이용해서 해결.