[백준] 1699번: 제곱수의 합

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

1699번: 제곱수의 합

DP를 이용해서 푸는 문제.

풀이의 핵심은 N의 제곱수 항의 최소개수를 구하고 싶다면, N에서 N보다 작거나 같은 제곱수를 뺀 값을 구한 뒤, 그 수의 제곱수 항의 최소개수 + 1을 하면 된다.

(처음에 알고리즘을 잘못 짰더니 시간초과에 걸렸다 ㅠ_ㅠ)

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

int dp[100001];

int main() {
	int N;
	cin >> N;

	dp[0] = 0;

	for (int i = 1; i <= N; i++) {
		int result = i;
		for (int j = 1; j*j <= i; j++) {
			result = min(dp[i - j * j] + 1, result);
		}
		dp[i] = result;
	}

	cout << dp[N];

	return 0;
}