백준 17626 Four Squares (c++) : 피너클

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

17626번: Four Squares

dp문제다.

개인적으로 탑 다운 방식을 좋아하지만 이 문제는 계산량때문인지 계속해서 오류가나 바텀 업으로 풀었다.

arr[0] = 0;
arr[1] = 1;

arr[0]은 제곱수들이 들어가는 배열이고 arr[1]은 1 * 1을 미리 초기화한것이다.

for (int i = 2; i <= n; i++) {
	arr[i] = 50001;

n까지 반복하며 arr[i]는 50001로 초기화해놓는다. 절대 나오지 않을 높은수로 하면된다.

	for (int j = 1; i - j * j >= 0; j++) {
		arr[i] = min(arr[i], arr[i - j * j] + 1);
	}
}

arr[50]을 알고싶다고 했을때 

arr[50] = min(arr[50], arr[50 - 1 * 1] + 1);

arr[50] = min(arr[50], arr[50 - 2 * 2] + 1);

arr[50] = min(arr[50], arr[50 - 2 * 2] + 1);

이걸 계속해서 반복하는것이다.

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[50001];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	arr[0] = 0;
	arr[1] = 1;
	for (int i = 2; i <= n; i++) {
		arr[i] = 50001;
		for (int j = 1; i - j * j >= 0; j++) {
			arr[i] = min(arr[i], arr[i - j * j] + 1);
		}
	}
	cout << arr[n] << endl;
}