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

---

이 문제를 처음에, 단순하게 특정 숫자와 가장 가까운 제곱수를 구하고, 특정 숫자와 제곱수의 차이에 해당하는 dp값을 더하는 방식으로 접근을 했었다.

 

예를 들어, 초기값으로 dp[1]= 1, dp[2]=2(1+1이므로 2개) , dp[3]=3(1+1+1 이므로 3개) 를 설정한 뒤, 

 

만약 18이라면, 18과 가장 가까운 제곱수는 16이기 때문에, dp[18]=1(16이므로 갯수 하나 소요)+dp[2] 와 같은 방식으로 말이다.

 

즉, 이와 같은 방식을 사용하면 18 = 4의 제곱 + 1의 제곱 + 1의제곱 = 총 갯수 3개가 나오는데, 

 

사실 18 = 3의제곱 + 3의제곱 = 2개 가 더 최소갯수이다.

 

그래서, 다른 방법으로 다시 접근해야 했다.

 

먼저, 특정 숫자에서 제곱수를 추출하는 것은 필수적이다. 하지만, 그게 무조건 가장 가까운 제곱수가 아닐 수 있다는 점이다.

 

따라서, 특정 숫자보다 작은 모든 제곱수를 하나씩 넣어 비교해보는 과정이 필요하다.

 

dp[] 에는 해당 숫자의 최소 제곱수 갯수를 기록할 것이다.

 

특정 숫자에서 제곱수를 빼는(감산하는) 과정은 제곱수의 갯수에 +1 을 더하는 과정과 같다.

 

 

---

예를 들어, 17의 최소 제곱수 갯수를 구한다고 하면, 바텀업 방식에 의해 dp[16] 까지는 다 채워져 있다고 가정하자.

 

17 이하의 제곱수는 1, 2, 3 ,4 이 있다.

 

1. 제곱수 4를 뺄 때,
   
   17 - 16 = 1 이고 17에서 16을 빼는 과정에서 4의 제곱이 분리되었으므로 dp[17] = dp[1] + 1 이 된다.
   
   
2. 제곱수 3을 뺄 때,
   
   17 - 9 = 8 이고, 17에서 9 를 빼는 과정에서 3의 제곱이 분리되었으므로 dp[17] = dp[8] +1 이 된다.
   
   
3.  제곱수 2를 뺄 때,
   
   17 - 4 = 13 이고, 17에서 4 를 빼는 과정에서 2의 제곱이 분리되었으므로 dp[17] = dp[13] + 1 이 된다.
   
   
4. 제곱수 1을 뺄 때,
   
   17 - 1 = 16 이고, 17에서 1을 빼는 과정에서 1의 제곱이 분리되었으므로 dp[17] = dp[16] + 1 이 된다.

 

특정 숫자보다 작은 제곱수를 빼고 남은 값의 dp값을 더하고, 이들 중 최솟값을 기록하면 최소 제곱 수가 기록이 된다.

 

이 규칙을 dp[1] 부터 dp[input] 값 까지 적용한 뒤 dp[input]값을 추출하면 답이 나온다!

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int input = scanner.nextInt();
		int[] dp = new int[input + 1];
		for (int i = 1; i <= input; i++) {
			dp[i] = i;
			for (int j = 1; j * j <= i; j++) {
				dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
			}
		}
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[input]);
	}
}