[백준] 17626 - Four Squares

https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

보자마자 dp 문제라 생각하였습니다. 자연수가 어떤 제곱수와 몇 번 더해서 만들어지게 되는데 그 자연수에 제곱수를 뺄 때마다 또 하나의 자연수가 나오기 때문입니다. 예를 들어 dp[26]은 dp[26 - 1^2] + 1, dp[26 - 2^2] + 1, ... dp[26 - 5^2] + 1 중 최소값입니다. 그래서 DP 함수를 선언해 재귀로 돌렸습니다.

 

#include <iostream>
#define MAX 50001
#define INF 100000000
using namespace std;

int dp[MAX];
int n;

int DP(int num) {
    if (dp[num] != INF)
        return dp[num];

    for (int i = 1; i * i <= num; i++)
        dp[num] = min(dp[num], DP(num - i * i) + 1);

    return dp[num];
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i <= n; i++)
        dp[i] = INF;

    dp[0] = 0;
    dp[1] = 1;
    cout << DP(n) << "\n";

    return 0;
}