백준 1699번: 제곱수의 합

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

1699번: 제곱수의 합

 

처음에 재귀함수로 풀다가 계속 시간초과가 나서 

 

dp로 풀었다

 

 

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;

int n, ans = INT_MAX;
vector<int> v;

int dp[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    fill(dp+1, dp + 100001, INT_MAX);
    cin >> n;

	for (int i = 1; i * i <= n; i++) {
        int tmp = i * i;
        for (int j = 0; j <= n; j++) {
            if (j - tmp >= 0) {
                dp[j] = min(dp[j], dp[j - tmp] + 1);
            }
        }
	}


    cout << dp[n] << '\n';

    return 0;
}