[백준 10448] 유레카 이론 (C++)

입력으로 들어올 숫자의 최대값은 1,000이기 때문에 가장 가까운 삼각수를 구하면 T44 = 990이다.
삼각수 T1 (1) ~ T44 (990) 를 이용해 세 개의 삼각수의 합으로 주어진 숫자를 구할 수 있는지 확인하면 되는데,

삼각수의 범위가 1~44이므로 최악의 경우 44*44*44 가 걸려 O(N^3) 안에 답을 찾을 수 있다.

 

---

 

C++)

#include <iostream>
#define MAX_NUM 45
using namespace std;

int arr[MAX_NUM + 1];

int FindAnswer(int number) {
	for (int i = 1; i <= MAX_NUM; i++) {
		for (int j = i; j <= MAX_NUM; j++) {
			for (int k = i; k <= MAX_NUM; k++) {
				if (arr[i] + arr[j] + arr[k] == number)
					return 1;
			}
		}
	}

	return 0;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	for (int i = 1; i <= MAX_NUM; i++)
		arr[i] = arr[i - 1] + i;

	int t, temp;
	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> temp;
		cout << FindAnswer(temp) << "\n";
	}

	return 0;
}