제곱수의 합

#include <stdio.h>
#include <math.h>
int p[100001];
int a[100001];

int get_max(int a, int b) {
	return a > b ? a : b;
}
int get_min(int a, int b) {
	return a < b ? a : b;
}

int main() {
	//freopen("input.txt", "rt", stdin);
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		p[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j * j <= i; j++) {
			p[i] = get_min(p[i], p[i - j * j] + 1);
		}
	}
	printf("%d", p[n]);
	

	return 0;
}