[백준] 10448번 유레카 이론

10448번: 유레카 이론

K가 3가지의 삼각수로 표현될 수 있는지 구하려면

삼각수를 먼저 구해준 후 3중 for문으로 세 삼각수의 합이 K가 되는 경우 1, 안 되는 경우 0을 출력하면 된다.

 

자연수 K의 범위가 1000까지이므로 삼각수 Tn은 T44(990)까지만 구해주고

T1에서 T44까지 세 번 돌리며 비교하면 끝

불필요한 반복을 줄이기 위해 중간 중간 break를 걸어준다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int Tn[45] = { 0 };
	for (int i = 1; i < 45; i++) Tn[i] = i*(i + 1) / 2;

	int T, K;
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> K;
		int finish = 0;
		for (int i = 1; i < 45; i++) {
			if (Tn[i] >= K) break;

			for (int j = 1; j < 45; j++) {
				if (Tn[j] >= K - Tn[i]) break;

				for (int k = 1; k < 45; k++) {
					if (Tn[k] > K - Tn[i] - Tn[j]) break;
					else if (Tn[k] + Tn[j] + Tn[i] == K) {
						cout << "1\n";
						finish = 1;
						break;
					}
				}
				if (finish == 1) break;
			}
			if (finish == 1) break;
		}
		if (finish == 0) cout << "0\n";
	}
	return 0;
}