백준 문제 풀이 - Four Squares 17626번

📜 문제 이해하기

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5²과 1²의 합이다; 또한 4² + 3² + 1²으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125² + 6² + 1² + 1²라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105² + 15² + 8² + 5².
자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

💡 문제 재정의

숫자를 최소 갯수의 제곱수로 표현해라.

✏️ 계획 수립

1부터 N까지 최소 제곱수를 순서대로 구해가면 된다. 이 때 이미 계산한거는 다시 구할 필요없이 동적 계획법을 통해 값을 구한다.
만약 값이 46이라면 46은 아래의 값들이 존재할 것이다.
46 = 1² + 45
46 = 2² + 42
46 = 3² + 37 ...
따라서 46의 최소 제곱수의 합은 1 + dp[45] or 1 + dp[42] or 1+ dp[37] ...
이런식으로 서술할 수 있다. 이 값을 모두 구해서 가장 작은 개수를 저장해가면서 나가면 된다.

💻 계획 수행

#include <bits/stdc++.h>

using namespace std;

int main() {
    int dp[50001];
    dp[1] = 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int num;
    cin >> num;

    for (int i=1; i<=num; i++){
        dp[i] = dp[1] + dp[i-1];
        for (int j=2; j*j<=i; j++)
            dp[i] = min(dp[i], 1 + dp[i-j*j]);
    }
    cout << dp[num] << '\n';
}

🤔 회고

동적 계획법을 통해 풀 수 있는 문제였다. 동적 계획법은 점화식을 세우는 것이 가장 힘들고 역시 나에게 제일 어려운 알고리즘이었다. 계속 연습을 통해 익숙해지도록 노력해보자.