백준 17626번 : Four Squares

문제 링크 : www.acmicpc.net/problem/17626

내 풀이1(2021.1.22.) :

#include <iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n; cin >> n;
	bool stop = false;
	int a, b, c, d;
	for (a = 0; a < 224; a++) {
		for (b = a; b < 224; b++) {
			for (c = b; c < 224; c++) {
				for (d = c; d < 224; d++) {
					if (a * a + b * b + c * c + d * d == n) {
						stop = true;
						break;
					}
				}
				if (stop) break;
			}
			if (stop) break;
		}
		if (stop) break;
	}

	int cnt = 0;
	if (a != 0) cnt++;
	if (b != 0) cnt++;
	if (c != 0) cnt++;
	if (d != 0) cnt++;

	cout << cnt;

	return 0;
}

방법 : 브루트 포스

 

내 풀이2(2021.1.22.) :

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

using namespace std;

int dp[50001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n; cin >> n;

	for (int i = 1; i <= n; i++) {
		dp[i] = 4;
	}
	
	for (int i = 1; i * i <= 50000; i++) {
		dp[i * i] = 1;
	}

	for (int i = 2; i <= n; i++) {
		int j = (int)sqrt(i);
		for(int j = 0; i - j * j > 0; j++){
			dp[i] = min(dp[i], dp[i - j * j] + dp[j * j]);
		}
	}

	cout << dp[n];

	return 0;
}

방법 : DP