백준 17626 (Four Squares) c++

문제

17626번: Four Squares

n이 주어지면 n의 제곱수로 이루어진 개수를 구하는 문제입니다.

예를 들어 n이 10이면

10 = 3^2 + 1^2 

총 2개가 됩니다.

 

규칙을 찾아보면 제곱수 (4, 9, 16, 25, ,,,,,) 들은 항상 개수가 1입니다.

즉 제곱수가 최소로 이루어져야 하므로 n 이하의 제곱수를 중심으로 살펴봐야합니다.

예를 들어 n이 12 라면

n이하의 제곱수는 1, 4, 9가 있습니다. 

점화식을 세워보면

dp[12] = dp[1] + dp[12 - 1 ] = dp[1] + dp[11]

dp[12] = dp[4] + dp[12 - 4] = dp[4] + dp[8]

dp [12] = dp[9] + dp[12 - 9] = dp[9] + dp[3]

저 중에 가장 작은 것을 갱신해 주면 됩니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int dp[50001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        int max = MAX;
        for (int j = 1; j * j <= i; j++) {
            int temp = i - j * j;
            max = min(max, dp[temp]);
        }
        dp[i]=max + 1;
    }
    cout << dp[n];
    return 0;
}