1699번 제곱수의 합

문제 링크

제곱수의 합

문제 풀이

동전2과 비슷한 문제이다. N이 최대 100,000 이므로 제곱수는 1 부터 316 까지 사용가능하다. 이를 하나씩 써가며 최소 개수를 센다.

구현

#include <iostream> 
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 987654321;
const int SIZE = 316;

int N, cache[100001][SIZE + 1];

int solve(int remain, int num) {
    if (remain == 0) return 0;
    if (num == 0) return INF;

    int& ret = cache[remain][num];
    if (ret != -1) return ret;

    ret = solve(remain, num - 1);
    if (remain >= num * num)
        ret = min(ret, solve(remain - num * num, num) + 1);
    return ret;
}

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

    cin >> N;
    memset(cache, -1, sizeof(cache));

    cout << solve(N, SIZE);
    return 0;
}