[ 백준 1699 ] 제곱수의 합 (C++)

백준의 제곱수의합(1699) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 주어진 숫자를 제곱수의 합으로 나타냈을 때 가장 최소의 항의 갯수를 출력하는 문제이다.

   본인은 문제 풀이 과정에서 가장 최소 항의 갯수를 저장하는 DP[] 1차원 배열을 사용하였다.

   DP[a] = b 의 의미는 "a라는 숫자를 제곱수의 합으로 나타낼 수 있는 최소항의 갯수는 b개 입니다."

   그럼 a를 1의 제곱의 합으로만 나타낸다면, 항의 갯수는 몇개일까? 아마 a개일 것이다.

   3을 1의 제곱의 합으로만 나타낸다면 1^2 + 1^2 + 1^2 으로 나타낼 수 있을 것이고 항의 갯수는 3개가 된다.

   모든 값들은 위에서 말한 값과 비교를 할 것이다.

   3은 위의 경우가 답이지만, 4인 경우에는 1의 제곱을 4번 더하는 것보다, 2의 제곱을 2번 더하는 것이 최소의 항의 갯수가

   되고, 본인은 윗줄에 밑줄 그어진 4번과 2번을 비교하는 식으로 생각을 했다.

2) 그렇다면 1)에서 말한 내용을 점화식으로 표현해보도록 하자.

   어떠한 수를 제곱했을 때, 우리가 찾고자 하는 특정 값 x보다 작은 값을 갖는 값들을 생각해보자...

   무슨소리인지 나도 모르겠다. 더욱 구체적이고 쉽게 알아보자.

   숫자 5를 특정 값 x라고 생각하고 가정해보겠다.

   5 = 1의 제곱을 5번 더하는 방식 or 2의 제곱 + 1의 제곱을 더하는 방식 이렇게 총 2가지의 방식이 있다.

   위에서 설명한 내용에 입각해서 다시 말해보면

   "어떠한 수를 제곱을 했을 때, 우리가 찾고자 하는 특정 값 5보다 작은 값들은 1과 2가 있습니다" 라는 의미이다.

   위의 내용을 한번만 더 생각을 해보면, DP[5]의 값은 2의 제곱에서 1의 제곱을 더한경우, 혹은 1의 제곱에서 2의 제곱을

   더해서 만들어진 경우의 최소 항의 갯수가 답이 될 것이다.

   즉 점화식이 DP[x] = Min(DP[x], DP[x- a * a]) 가 될것이다. 여기서 a = 제곱했을 때, x보다 작은 값들을 의미한다.

3) 위의 내용을 반복문을 통해서 구현을 하면 되는데, 이 때 계속해서 초기값을 설정해줘야 할 것이 있다.

   1)에서 말한 DP[a] = a 라는 값이다. 3을 1의 제곱으로만 나타내면 항의 갯수는 3개 인것 처럼 !

[ 소스코드 ]

 

#include<iostream>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N;
int DP[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        DP[i] = i;
        for (int j = 1; j * j <= i; j++)
        {
            DP[i] = Min(DP[i], DP[i - j * j] + 1);
        }
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}