제곱수의 합

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

1699번: 제곱수의 합

d[n] = min (d[n - i ^ 2] ) + 1 ( 1 <= i ^ 2 <= N)

시간 복잡도 O( N * N ^ 1/2)

최소값 구하는 문제 --> 초기값 설정 중요!!

d[i]는 i를 넘을 수가 없다 고로, i로 설정하자

 

내 코드

#include <iostream>
#include <cstring>
 
using namespace std;
 
int d[100000];
 
int main()
{
    memset(d, -1, sizeof(d));
 
    d[1] = 1;
 
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (j * j > i)
                break;
            else if (j * j == i)
            {
                d[i] = 1;
                break;
            }
            if (d[i] == -1 || d[i - j * j] < d[i])
                d[i] = d[i - j * j] + 1;
        }
    }
 
    cout << d[n];
 
    return 0;
}

#include <iostream>
using namespace std;
int d[100001];
int main() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        d[i] = i;
        for (int j=1; j*j <= i; j++) {
            if (d[i] > d[i-j*j]+1) {
                d[i] = d[i-j*j]+1;
            }
        }
    }
    cout << d[n] << '\n';
    return 0;
}