(JAVA) 백준 1699번 : 제곱수의 합

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

1699번: 제곱수의 합

 

안녕하세요.

 

DP(동적 프로그래밍) 문제 중 하나로,

 

처음에 깊게 생각하지 않아서 한 번 틀리고, 방향을 바꿔 맞출 수 있었다.

(사실 두 번 틀렸다.)

 

 

이 문제의 핵심은 이거다.

 

구하려고 하는 수 N의 제곱수의 합은 1 ~ N 까지의 수 중 제곱수인 수 + (n - 제곱수) 의 최소 제곱수 갯수 중 최소인 값 이다.

 

 

예를 들어보자.

 

13 = 2^2 + 2^2 + 2^2 + 1^1 이 될 수도 있지만,

최소인 경우는 역시 3^3 + 2^2 이다.

 

즉, 1 ~ 13중에서 제곱수인 것은 1, 4, 9 가 되고 이들의 최소 제곱수는 1이다.

 

그럼 13의 제곱수의 합이 최소가 되는 경우는 무엇이냐?

 

(13 - 1) 의 최소 제곱수의 합, (13 - 4)의 최소 제곱수의 합, (13 - 9)의 최소 제곱수의 합

 

중 가장 작은 값과 +1(1, 4, 9 등 제곱수의 개수는 1개 이니까) 이 된다.

 

 

이해했는가?

 

가장 개수가 적으려면 제곱수(1개) 를 포함해야 한다. 왜? 1개니까!! 1을 더하는 값이 최소가 되지 않겠는가?

 

 

이를 알면 별도의 매커니즘은 스스로 생각해서 작성할 수 있다.

 

필자는 헷갈려서 해설을 조금 참고했지만...

 

 

하단 소스코드를 참고하면 된다.

 

 

감사합니다!

 

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	// 동적 프로그래밍
	// 제곱수의 합
	// dp[n] = (a = n-1 ~ n/2, b = n - a) 일 때, dp[a] + dp[b] 의 최솟값
	public class p1699 {
	static int[] dp;
	public static void main(String args[]) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.valueOf(br.readLine());
	dp = new int[100001];
	// double sqrt = Math.sqrt((double) n);
	// 제곱근 존재하는 수만 먼저 설정 -> 안해도된다.
	// 대신, 1이 몇 개 존재하는지 초기 설정을 해준다. (최댓값으로 초기 설정)
	for(int i = 1; i <= n; i++) {
	dp[i] = i;
	}
	for(int i = 1; i <= n; i++) {
	// 최소가 되는 제곱수 = n의 이전 수 들 중 제곱수 + n - 제곱수의 최수항 개수
	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]);
	}
	}

view raw p1699.java hosted with ❤ by GitHub