문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

---

풀이

풀이과정

시행착오

#include <iostream>
#include <algorithm> 
#include <vector>
#include <cmath> // sqrt 함수 사용하려면 필요!

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // [ 풀이 ]
    // 제곱해서 N을 넘지 않는 최대 수를 일단 구한다.
    // 그 수부터 시작해서, 밑으로 1씩 감소하면서 채워나간다.
    // 채워나가면서 N에서 계속 빼준다.
    // 0이 되면 종료

    int n;
    cin >> n;
    int count = 0;

    while(true){
        //n을 넘지 않는 최대 제곱수 구하기
        int maxInt = (int)(sqrt(n));
        
        //n에서 제곱한 걸 빼주기
        n -= pow(maxInt, 2);
        count++;

        //n이 0이 되면 break;
        if(n == 0)
            break;
    }
    cout << count;

    return 0;
}

맨 처음 작성했던 코드이다.
예제에 제시된 케이스들은 모두 정상적으로 작동하나, 게시판에서 반례를 찾아봤을 때 '18'의 경우 2가 출력되어야 하는데 3이 출력되었다.

정답은 $3^2 + 3^2$를 해서 2인데,
내 코드는 $4^2 + 1^2 + 1^2$를 해서 3이 출력된 것이다.

즉 내가 작성한 알고리즘은 너무나 단순했고 옳지 않다. 무조건 최대가 되는 정수부터 시작하면 안 된다.

모든 케이스를 저장해놓고, 최소가 되는 경우를 출력해야 한다.
즉 DP(Dynamic Programming)을 사용해야 한다.

최종 코드

#include <iostream>
#include <algorithm> 
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    int dp[100001];
    for(int i = 0; i <= N; i++) dp[i] = i; // 초기화-최악의 경우: 1^2을 i번 더하는 것

    for(int i = 1; i <= N; i++) // 1부터 N까지 1씩 증가하면서 반복.(하나씩 올라가면서 그 전의 수의 정답을 저장함)
    {
        for(int j = 1; j * j <= i; j++)
        {
            dp[i] = min(dp[i], dp[i - j * j] + 1); //여기서 +1은 새로 추가되는 항을 의미함
        }
    }
    cout << dp[N];

    return 0;
}