https://www.acmicpc.net/problem/1699
Bottom-Up 방식을 이용한 DP를 활용하여 배열을 구성하였다.
일단 최대값은 1의 제곱으로만 구성된 경우이다. 따라서 자기 자신의 값인, dp[i] = i 로 초기화한다.
그리고 가장 작은 제곱수부터 가장 가까운 제곱수까지 루프를 돌면서 최소 개수를 찾는다.
예를 들어서 8을 제곱수의 합으로 나타낼 때, 그 항의 최소 개수를 구해보자.
1 = 1^2
2 = 1^2 + 1^2
3 = 1^2 + 1^2 + 1^2
4 =1^2 + 1^2 + 1^2 + 1^2, 2^2
5 =1^2 + 1^2 + 1^2 + 1^2 + 1^2, 2^2 + 1^2
6 =1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2, 2^2 + 1^2 + 1^2
7 =1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2, 2^2 + 1^2 + 1^2 + 1^2
8 =1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2, 2^2 + 2^2
위의 예시를 보면 8의 경우 8과 가장 가까운 제곱수인 4(2^2)를 8에서 뺀 4의 dp배열의 값을 활용했음을 알 수 있다.
식으로 표현하면 다음과 같은데, dp[8-4(2*2)] + 1 여기서 +1은 식에서 가까운 제곱수를 구하기 위해 빼준 값에 해당한다.
계속해서 값을 구하다보면 규칙을 찾을 수 있다.
자신의 제곱근까지의 값의 제곱수까지 탐색이 가능하고, 위의 식에 대입해가면서 가장 최소의 값을 찾으면 된다.
dp[i] = Math.min(dp[i], dp[i - j^2] + 1)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n + 1];
for(int i = 1; i <= n; i++) {
dp[i] = i;
for(int j = 1; j*j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - (j*j)] + 1);
}
}
System.out.println(dp[n]);
}
}