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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

설명을 보기에 앞서, 이제부터 나올 내용들을 보다 간략하게 표현하기 위해서 수식을 하나 이용해보자.

F[A] = B 라는 수식을 사용할 것인데, F[A] = B의 의미는 "숫자 A를 제곱수의 합으로 나타냈을 때, 항의 최소갯수는 B개입니다." 를 의미한다.

예를 들어서 문제의 설명에도 나와있는 11이라는 숫자를 예로들면 11같은 경우에는 5개의 항으로도 표현할 수 있지만, 3개의 항으로도 표현이 가능하기 때문에 F[11] = 3 이 된다.

그럼 지금부터 4 , 8 , 9 를 만드는 경우들을 통해서 문제에 접근해보자.

# Case1 : 제곱수의 합으로 '4'만들기.

먼저 제곱수들의 합으로 4를 만들 수 있는 경우를 모두 적어보자.

1. 1 + 1 + 1 + 1

2. 4 (2^2)

이렇게 2가지 경우가 있다. 그 중 항의 최소갯수는 1개이다.

F[4] = 1

# Case2 : 제곱수의 합으로 '8'만들기.

먼저 제곱수들의 합으로 8을 만들 수 있는 경우를 모두 적어보자.

1. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2. 1 + 1 + 1 + 1 + 4

3. 4 + 4 

위와 같이 3가지 경우가 존재한다. 딱 봐도 알 수 있듯이 위의 경우에서 항의 최소갯수는 2개이다.

물론 위보다 더 많은 경우들이 존재하지만, 일단은 위의 경우들만 적어보겠다.

F[8] = 2

# Case3 : 제곱수의 합으로 '9'만들기.

먼저 제곱수들의 합으로 9를 만들 수 있는 경우를 모두 적어보자.

1. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2. 1 + 1 + 1 + 1 + 1 + 4

3. 1 + 4 + 4

4. 9 (3^2)

위와 같이 4가지 경우가 존재한다. 위의 경우에서 항의 최소갯수는 1개이다. 즉 ! F[9] = 1 이라는 것인데, 위의 경우들을 하나하나 다 비교하는 것이 아니라 어떻게 비교할지에 대해서 이야기해보자.

먼저, 어떤 숫자 K가 존재한다면, 1의 제곱인 1을 K번 사용해서 그 숫자를 만들 수 있다.

위에서 이야기한 Case1과 Case2, 3에서 1번 경우들을 보면 모두 1을 4번, 8번, 9번 사용해서 만든 것이다.

즉, 어떤 숫자 K는 K개의 항의 갯수를 통해서 그 숫자를 만들 수 있다.

또한, 그 어떤 숫자의 제곱에 해당하는 숫자는 그 항의 갯수가 1개이다.

1, 4, 9, 16, 25... 이렇게 어떤 숫자의 제곱에 해당하는 숫자는 그 항의 갯수가 1개이다.

그럼 이제 Case2('8'만들기) 에 집중해보자.

Case2에서 1번 경우부터 살펴보자.

"1 + 1 + 1 + 1 + 1 + 1 + 1 + 1" 로 8을 만든 경우인데, 이 경우를 이렇게 나눠서 생각해보자.

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

빨강색 부분과 파랑색 부분으로 나눠서 생각을 해보자.

그럼 빨강색 부분은 '7'을 이루고 있고, 파랑색 부분은 '1'을 이루고 있다.

즉 ! '8'이라는 숫자를 제곱수의 합으로 나타낼 수 있는 경우 중 하나는 '7'을 만들 수 있는 제곱수의 항의 갯수에 '1'이라는 1개의 항을 더 더한 항의 갯수로 나타낼 수 있다는 것이다.

두 번째 경우를 보자.

"1 + 1 + 1 + 1 + 4" 로 8을 만든 경우인데, 이 경우를 이렇게 나눠서 생각해 볼 수 있다.

1 + 1 + 1 + 1 + 4

이렇게 빨강색을 친 부분으로 '4'를 만들고 난 후에, 거기에 '4'를 더한 꼴로 나타낼 수 있다는 것이다.

즉 ! '8'이라는 숫자를 제곱수의 합으로 나타낼 수 있는 경우 중 하나는 '4'를 만들 수 있는 제곱수의 항의 갯수에 '4'라는 1개의 항을 더 더한 항의 갯수로 나타낼 수 있다는 것이다.

세 번째 경우를 보자.

세 번째 경우는 "4 + 4"로 8을 만든 경우인데, 이 경우 또한 마찬가지로 4 + 4 로 나타내낼 수 있다.

특히 2번 경우와 3번 경우는 비교에 의미가 없는 경우들이다.

왜냐하면 1 + 1 + 1 + 1 + 4 와 4 + 4 모두 빨강색으로 표시된 부분이 공통적으로 '4'를 이루고 있다는 점 때문이다.

그럼 하나는 '4'를 4개의 항으로 표시한 것이고, 다른 하나는 '4'를 1개의 항으로 표시한 것인데, 최소항의 갯수를 구해야 하는 우리 입장에서 굳이 전자를 선택할 이유가 없다. 더군다나 ! 우리는 '4'라는 숫자를 만들 때 필요한 최소 항의 갯수를 이미 알고 있다. 어떻게 ? Case1에서 계산을 했기 때문이다.

그럼 결과적으로 우리에게 남은 경우들을 살펴보면 첫 번째 경우인 "1 + 1 + 1 + 1 + 1 + 1 + 1 + 1" 과 세 번째 경우인

"4 + 4" 를 비교하면 된다는 것이다.

다시 한번 빨간부분과 파랑 부분으로 나눠보면

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

4 + 4 이렇게 될 것이고, 이 2개의 식을 우리가 사용하는 수식으로 나타내보면..

F[8] = Min(F[7] + 1 , F[4] + 1) 이 된다는 것이다.

위의 표시된 대로만 본다면, F[7] 이 마치 7개의 항을 사용해야 하는 것 처럼 적어놨지만, 사실은 더 적은 항의 갯수로 7을 표현할 수 있다.

그럼 '7'과 '4'라는 숫자가 나왔는데 이 숫자들은 어떻게 나오게 된 숫자들일까 ??? 우리는 현재 '8'이라는 숫자를 만들고 있는 것이다. 7은 '8'에서 1^2을 뺀 값이 되고, 4는 '8'에서 2^2을 뺀 값이 되는 것이다.

그럼 위의 수식에 들어간 숫자에서 '8'대신 'N'이라는 값을 넣어보자.

F[N] = Min(F[N - 1^2] + 1 , F[N - 2^2] + 1 , F[N - 3^3] + 1 , .... ] 이 된다는 것이다.

이를 점화식으로 사용해서 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N;
int DP[MAX];
// DP[a] = b : 숫자 a를 제곱수들의 합으로 표현할 때, 그 항의 최소갯수는 b개입니다.
 
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;
}