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

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

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

1699번: 제곱수의 합

 

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        dp = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            dp[i] = i;
            for (int j = 1; j * j <= i; j++) {
                if (dp[i] > dp[i - j * j] + 1) {
                    dp[i] = dp[i - j * j] + 1;
                }
            }
        }
        System.out.println(dp[N]);

    }
}

 

[설명]

 

dp[1]  =  1  => 1^2

dp[2]  =  2  => 1^2 + 1^2

dp[3]  =  3  => 1^2 + 1^2 + 1^2

dp[4]  =  1  => 2^2

dp[5]  =  2  => 1^2 + 2^2

dp[6]  =  3  => 1^2 + 1^2 + 2^2

dp[7]  =  4  => 1^2 + 1^2 + 1^2 + 2^2

dp[8]  =  2  => 2^2 + 2^2

dp[9]  =  1  => 3^2

dp[10]  =  2  => 1^2 + 3^2

 

dp[1] , dp[4], dp[9], dp[16] 같이 어떤 수의 제곱인 수는 제곱수가 1개 있다. 그 점을 이용해 N 에서 dp[1] , dp[4], dp[9] ... 을 뺀 후 1을 더해 구한다. 1을 더하는 이유는 dp[1] , dp[4], dp[9] ... 가 1을 대신하기 때문이다.

예를 들어 15는

(15 - 1) 의 최소 제곱수의 합 + 1   // 1 = 1^1
(15 - 4)의 최소 제곱수의 합 + 1   // 4 = 2^2
(15 - 9)의 최소 제곱수의 합 + 1  /  9 = 3^3
중 가장 작은 값이다.