백준1699 - 제곱수의 합

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

1699번: 제곱수의 합

점화식 문제다. 각각의 제곱수를 최소 갯수로 더하여 내가 찾는 수가 나오도록 하면 된다.

 

ex1.) 20, 루트 20은 4.xxxxxxx니까 최대 4의 제곱까지만 더한다.

1의 제곱 + 19를 만드는데 필요한 수의 갯수(1, 3, 3) : 1 + 3 = 4

2의 제곱 + 16을 만드는데 필요한 수의 갯수(4) : 1 + 1 = 2

3의 제곱 + 11을 만드는데 필요한 수의 갯수(1, 1, 3) : 1 + 3 = 4

4의 제곱 + 4를 만드는데 필요한 수의 갯수(2) : 1 + 1 = 2

20은 최소 2개로 만들 수 있다.

 

ex2.)12, 루트 12는 3.xxxxxx니까 최대 3의 제곱까지만 더한다.

1의 제곱 + 11을 만드는데 필요한 수의 갯수(1, 1, 3) : 1 + 3 = 4

2의 제곱 + 8을 만드는데 필요한 수의 갯수(2, 2) : 1 + 2 = 3

3의 제곱 + 3을 만드는데 필요한 수의 갯수(1, 1, 1) : 1 + 3 = 4

12는 최소 3개로 만들 수 있다.

 

다음과 같은 과정을 이중 포문을 돌려 완성한다.

 

#include <iostream>
#include <cmath>
using namespace std;

int mat[100001]; //10만개 수에 대한 DP결과값을 찾는다.

int main() {
	int what; //찾는 수를 입력
	int check; //제곱하였을 때 10만에 가장 가까운 수가 무엇인지 찾는다.

	cin >> what; //찾는 수 입력

	check = sqrt(100000); //10만까지 자연수 중 제곱하였을 때 가장 10만에 가장 가까운 수를 찾는다.

	//10만 범위 중 오직 하나의 자연수의 제곱만으로 만들어지는 수를 1로 초기화한다.
	for (int i = 1; i <= check; i++) {
		mat[i * i] = 1;
	}

	//DP를 이용하여 각 구현
	for (int i = 1; i <= what; i++) {
		for (int j = 1; j <= int(sqrt(i)); j++) {
			if (!mat[i] || mat[i] > mat[i - j * j] + mat[j * j]) { //DP값이 없는 곳이나 구해진 DP값보다 현재 수를 이용하여 구한 DP값이 작으면
				mat[i] = mat[i - j * j] + mat[j * j]; //DP값 갱신
			}
		}
	}

	cout << mat[what]; //내가 찾는 수의 DP결과를 출력
}