[백준]Baekjoon1699(Dynamic Programming)

문제링크 : https://www.acmicpc.net/problem/1699

#include <iostream>
#include <algorithm>
#include <cmath>

#define SIZE 100001

using namespace std;

int memo[SIZE];
int main()
{
	long long N;
	scanf("%lld", &N);

	for (int i = 1; i <= N; i++) {
		memo[i] = i; //1의 제곱의 조합으로 이루어진 항의 갯수가 최댓값
		for (int j = 1; j*j <= i; j++) { //j제곱을 뺀 항중에서 최소갯수를 가진 것을 골라서 1을 더한것이 i항의 최소갯수
			if (memo[i - j*j] + 1 < memo[i])
				memo[i] = memo[i - j*j] + 1;
		}
	}
	cout << memo[N] << '\n';
}