[삼성 알고리즘] Dynamic Programming(제곱수의 합)

안녕하세요 이번 포스팅 내용은 동적프로그래밍으로 백준의 제곱수의 합 문제입니다.

 

제곱수의 합 문제는 어떤 임의의 수가 주어졌을 때 해당 임의의 수를 제곱수들만 가지고 만들어야 합니다. 이 때 제곱수들의 갯수가 최솟값이 되는 경우를 구하는 문제입니다.

 

 

1. 문제 이해

제곱수의 합 문제 이해를 돕기 위해 예시를 하나 들어보겠습니다.

만약 18이라는 숫자가 주어졌다면 18 = 4^2 + 1^2 + 1^2 혹은 3^2 + 3^2 등으로 만들 수 있으며 이 때 가장 적은 제곱수들로 18을 만드는 방법은

18 = 3^2 + 3^2로 output 2를 가지면 됩니다.

 

2. 식 만들기

1) 임의의 수의 양의 제곱근이 자연수 일때

만약 임의의 수의 양의 제곱근이 자연수라면 해당 문제는 최솟값을 구하는 것이기 때문에 '1'을 출력해주시면 됩니다.

 

2) 임의의 수의 양의 제곱근이 자연수가 아닐 때

만약 양의 제곱근이 자연수가 아니라면... 최솟값을 찾기 위해 비교 작업이 필요합니다.

먼저 N의 경우 N의 제곱근보다 큰 수의 제곱으로는 절대 이루어 질 수 없습니다. 때문에 해당 경우의 수를 제외하고

1< x < √N 의 범위에 해당하는 x값들의 제곱을 항으로 가졌을 때를 비교해감으로써 최솟 값을 구할 수 있습니다. 

 

해당 부분의 이해를 돕기 위해 예를 들어 설명하겠습니다.

먼저 18이라는 수가 주어졌다면 √18의 경우 4.xxxx가 됩니다. 즉 x 값은 1부터 4까지의 값이 됩니다.

 

1) x==1

x가 1인 경우 우리는 18 - x^2 의 최솟값 + 1(x=1 제곱수)을 해준 값이 18의 최솟값이 됩니다.

 

2) x==2

x가 2인 경우 우리는 18 - x^2의 최솟값 + 1(x=2제곱수)을 해준 값이 18의 최솟값이 됩니다.

 

3) x==3

x가 3인 경우 우리는 18 - x^3의 최솟값 + 1(x=3제곱수)을 해준 값이 18의 최솟값이 됩니다.

 

4) x==4

x가 4인 경우 우리는 18 - x^4의 최솟값 + 1(x=4제곱수)을 해준 값이 18의 최솟값이 됩니다.

 

즉 위 1)~4)의 경우들 중 최솟값이 바로 N=18일 떄의 최솟값 즉 answer이 되며 위 내용을 재귀 형식으로 구현함으로써 Top-Down 방식의 Dynamic Programming이 완성이되고 빠른 시간내에 답을 구할 수 있습니다.

 

3. 소스 코드

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

double arr[100001];

int square_root_count(int num) {
double buf = sqrt(num);
if (buf-(int)buf==0) {
return 1;
} else {
int min = 100000;
int sqrt_int = (int)buf;
for (int i = 1; i < buf; i++) {
int bufs = num - (int)pow(i, 2);
if (arr[bufs] == -1) {
arr[bufs] = square_root_count(bufs);
}
if (min > arr[bufs]) {
min = arr[bufs];
}
}
return min+1;
}
}
int main(void) {
int N;
cin >> N;
for (int i = 0; i < 100001; i++) {
arr[i] = -1;
}
cout << square_root_count(N) << endl;
return 0;
}