[백준 1699] 제곱수의 합

분류 : DP

 

요구사항

주어진 수가 최소 몇개의 제곱수들의 합으로 이루져있는가 구하기

 

풀이

d[i]= min(d[i] , d[i-j*j]+d[j*j])이다

바텀업 방식으로 아래에서부터 최소를 구해놓는다

d[i]가 가질 수 있는 제곱수 들은 앞에서 이미 구해놓았던 제곱수들의 합으로 이루어 질 수 있다

 

#include <iostream>
#include <algorithm>

using namespace std;
int n;
int d[100100];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= 100000; i++) d[i] = i;
	for (int i = 1; i*i <= 100000; i++) d[i*i] = 1;

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