acmicpc_1699(제곱수의 합)

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

int i, n;
int d[100001];
int main() {
	cin >> n;

	for (i = 0; i <= n; i++) 
		d[i] = i;
	for (i = 2; i <= n; i++) {
		for (int j = 2; j * j <= i; ++j) {
			d[i] = min(d[i], d[i - j * j] + 1);
		}
	}

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

너무 오랜만이네요..ㅎㅎ 스프링 부트가 재밌어서 공부하다 보니 알고리즘에 소홀하게 됐네욤..^^

이번 문제는 예전에 틀려서 도저히 모르겠어서 방치해뒀던 문제인데 이번 기회에 풀어보았답니다!(힌트 슬쩍 얻긴했음)

dp문제인데 생각보다 간단하게 제곱수 만큼 빼보면서 비교하면 되었던 문제!