1 = 1: 1
2 = 2: 2 = 1 + 1
3 = 3: 3 = 2 + 1 = 1 + 1 + 1
4 = 1: 4
5 = 2: 4 + 1
6 = 3: 4 + 2 = 4 + 1 + 1
7 = 4: 4 + 3 = 4 + 1 + 1 + 1
8 = 2: 4 + 4
9 = 1: 9
10 = 2: 9 + 1
11 = 3: 9 + 2 = 9 + 1 + 1
12 = 3: 4 + 4 + 4
13 = 2: 9 + 4
14 = 3: 9 + 5 = 9 + 4 + 1
...- 제곱수는 모두 1
- 제곱수를 제외하고 1은 없다
- 따라서 2로 만들 수 있는 것들은 모두 정답
- “제곱수* 제곱수”는 모두 2
- 모두 제곱수로 나타내는 것이 최솟값이다.
그나마 규칙을 발견한 게 이 정도다..
모두 제곱수로 구성해야만 최솟값이 되는 건 확실한데, 그 제곱수의 개수가 몇 개로 구성되는지의 규칙은 특정하기가 어려운 거 같다..
어쨌든 이 문제가 DP 문제니까 DP 식으로 생각을 해보면, N이라는 것이 만들어지는 게 이전의 구성들에서 최적값으로 만들어진다.
예를 들어
1. 3은 그보다 작은 숫자들의 합으로 만들 수 있는 케이스가 1과 2밖에 없어서 바로 결정된다.
2. 4는 제곱수라서 1로 바로 결정된다.
3. 5는 5보다 작은 수 1, 2, 3, 4 중에서
- 1 + 4 = 2 < 5 = 2 + 3라서 1 과 4의 합인 2로 결정된다.
- 물론 1과 4가 제곱수라서 제곱수들의 합은 바로 2다.
4. 6은 6보다 작은 수 1, 2, 3, 3, 4, 5 중에서
- 4와 2의 합으로 만드는 것이 제일 최솟값이라서 3으로 결정된다.
이런 식으로 N을 만들 때 이전의 결정된 DP 배열에서 최적의 조합을 골라서 결정하는 방식이다.
점화식으로 적어보자면 이렇게 된다.
DP[N] = min(DP[1] + DP[N-1], DP[2] + DP[N-2], ... )이 방식대로 코드를 짜서 제출해보니 통과는 됐다..
정답
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N 입력 받기
int N = Integer.parseInt(br.readLine());
// dp 배열 생성
int[] dp = new int[N + 1];
// dp
// 제곱수는 모두 1
for (int i = 1; i <= (int) Math.sqrt(N); i++) {
dp[i * i] = 1;
}
// 제곱수들의 합
for (int i = 1; i < (int) Math.sqrt(N); i++) {
for (int j = 1; j < (int) Math.sqrt(N); j++) {
int target = i * i + j * j;
if (target <= N && dp[target] == 0) {
dp[target] = 2;
}
}
}
// 탐색
for (int i = 3; i <= N; i++) {
if (dp[i] == 0) {
dp[i] = Integer.MAX_VALUE;
for (int j = 1; j <= (i + 1) / 2; j++) {
dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
}
}
}
// 출력
System.out.println(dp[N]);
}
}근데 아무리 생각해도 찝찝해서 gpt에게 한 번 물어봤다..
아... 정작 중요한 조건을 놓치고 있었다..
문제 이름도 그렇고, 문제 조건에도 나와 있듯이 제곱수다..
즉, 무조건 제곱수가 포함이 돼 있다는 것이고, 그 말은 N을 만들 때, 무조건 N = i^2 + N-i^2으로 구성된다는 것이다..
i^2으로 표현된 제곱수는 무조건 1이고, N-i^2을 생각해보면, 앞에 값들은 당연히 최소값으로 보장이 돼 있을테니까, DP[N-i^2]중에서 최솟값을 채택하면 정말 간단하게 해결되는 일이었다..
숫자를 마구잡이로 나열하다보니 정작 문제가 무엇인지를 놓치고 있었다..
재시도
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N 입력 받기
int N = Integer.parseInt(br.readLine());
// dp 배열 생성
int[] dp = new int[N + 1];
dp[1] = 1; // 초기값 설정
// dp
for (int i = 2; i <= N; i++) {
// 1. N = i^2
if (i == (int) Math.sqrt(i) * Math.sqrt(i)) {
dp[i] = 1;
// 2. N = j^2 + (N -j^2)
} else {
dp[i] = i; // 최악의 경우로 초기화
for (int j = 1; j * j < i; j++) {
dp[i] = Math.min(dp[i], 1 + dp[i - j * j]);
}
}
}
// 출력
System.out.println(dp[N]);
}
}