[BOJ] 1699번 : 제곱수의 합

1. problem : 

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

 

2. solution 1 :

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

int n;
int d[100005];

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

    for (int i = 1; i <= n; i++) {
        d[i] = i; // 가장 나쁜 경우는 1^2을 i번 사용
        for (int j = 1; j * j <= i; j++) {
            d[i] = min(d[i], d[i - j * j] + 1);
        }
    }

    cout << d[n] << '\n';
    return 0;
}

soure code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/1699.cpp

basic-algo-lecture/0x10/solutions/1699.cpp at master · encrypted-def/basic-algo-lecture