백준 1699. 제곱수의 합

(1) 1699. 제곱수의 합.

• 자연수 N은 그보다 작거나 같은 수들의 합으로 표현이 가능하다. 그중에서 최소 갯수를 사용해 표시하는 경우의 수를 구하시오.

• 네. 당연히 반복문 사용하면 풀릴줄알았습니다.

import java.awt.*;
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        int count = 0;
        while (N > 0) { // 10만 이하
            // N보다 작거나 같은 제곱수 찾기
            int sqrtN = (int) Math.sqrt(N);
            //System.out.println(sqrtN);
            int powN = (int) Math.pow(sqrtN, 2);
            N -= powN;
            count++;
        }

        System.out.println(count);
    }
}

• 근데 생각해보니까, 꼭 자신보다 작은것중에 최대 제곱으로 빼는식으로, 내림차순으로 빼도,
• 중간에 그것보다 작은것들의 합으로 표현이 되는 경우가 있을거라고 생각했습니다.
• 예를 들어, 17 = 9^2 + 4^2 + 1^2 인경우가 된다고 해도,
  6^2 + 5^2 가 있을지도 모른다고 생각했습니다. (두경우가 같은수라고 한다면)
• 근데 이런경우는, 반복문으로 풀수가 없습니다.
• 따라서 방법을 생각하고있는데, DP라고 하네요.
• 방법은 이렇습니다.

dp[1] = 1    (1^2)
dp[4] = 1    (2^2)
dp[9] = 1	 (3^2)

• 제곱수들의 수들은 모두 1입니다.
  따라서, dp[17]같은수의 경우

dp[17] = dp[16] + 1 or dp[13] + 1 or dp[8] + 1
or dp[1] + 1

• 로 표현이 가능합니다.
• 각각의 경우의 수를 구하면,

1. dp[17] = 2 (1^1 + dp[16])
2. dp[17] = 3 (2^2 + dp[13]) 
3. dp[17] = 4 (3^3 + dp[8])
4. dp[17] = 2 (4^4 + 1)

이중에서 최소 경우의수는 2입니다.
따라서 이걸 조건식으로 놔주면됩니다.

for (int i = 1; i <= N; i++){
	dp[i] = i;
	for (int j = 1; j * j <= N; j++){
    	if (dp[i] > dp[i - j * j] + 1){ 
        // 더 작은 경우가 있다면 최신화한다.
        	dp[i] = dp[i - j * j] + 1;
        }
    }
}

최종 코드

import java.awt.*;
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        int count = 0;
        // 또 dp야
        int[] 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;
                }
            }
        }

        // dp[1] = 1;
        // dp[4] = 1;
        // dp[9] = 1; -> 제곱수들은 모두 1개이다.
        // dp[8] = dp[7] + 1 or dp[4] + 1 중에 하나일 것이다.
        // N보다 작은 제곱수들로 빼준것 + 1 중에 더 작은게 있으면 그걸로 대체한다.


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

• 네, 또 dp 입니다.