백준 10448 유레카 이론 [BruteForce]

문제 링크: https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

문제 풀이

n의 크기가 1000밖에 되지 않기 때문에 모든 경우를 다 확인해보면 됩니다.

구하기에 앞서서, 50까지의 삼각수를 미리 구해놓고 풀면 간편합니다. (일일이 다시 구하지 않아도 되기 때문에)

n을 3개의 삼각수의 합으로 표현이 되면 1, 아니면 0으로 출력해주면 끝.

소스 코드

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

bool solve(vector<int>& v, int n)
{
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v.size(); j++)
		{
			for (int k = 0; k < v.size(); k++)
			{
				// 3개의 삼각수의 합으로 표현되는 자연수이면
				if (n == v[i] + v[j] + v[k])
				{
					return true;
				}
			}
		}
	}

	return false;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	int k;
	cin >> k;
	// 삼각수를 미리 구해 놓는다.
	vector<int> v;
	for (int i = 1; i <= 50; i++)
	{
		int t = (i * (i + 1)) / 2;
		v.push_back(t);
	}

	while (k--)
	{
		int n;
		cin >> n;
		if (solve(v, n)) cout << 1 << '\n';
		else cout << 0 << '\n';
	}
	return 0;
}