백준(BOJ) 10448번 유레카 이론

안녕하세요? 오늘은 백준 알고리즘 사이트 문제 중 하나인 10448번 유레카 이론을 풀어보겠습니다.

먼저 문제를 보겠습니다.

삼각수(triangle number)는 문제에서 보여지듯이 

입니다.

그리고 가우스는 최대 3개 삼각수의 합으로 모든 자연수를 표현할 수 있다고 증명하였습니다. 그리고 이 이론은 유레카 이론으로 알려져왔다고 합니다. 

문제는 어떠한 수가 주어졌을 때, 이 수가 3개의 삼각수로 표현이 가능한지 알아보고 표현이 가능하면 1, 가능하지 않다면 0을 출력하는 것입니다.

제가 접근한 방식은 문제에서 주어지는 입력 K는 3에서 1000사이의 값이기 때문에 1000 이상의 값은 무의미 하다는 것입니다. 

즉, 전 1에서부터 1000사이의 삼각수를 구하면 되고 그 수들을 가지고 가능한 케이스를 검사하는 방식을 택하였습니다. 

그럼 1000에 가장 가까운 n값을 찾기 위해 다음의 식을 사용하였습니다.

즉, n의 최댓값은 44이며, 즉 저희는 총 44개의 삼각수를 가지고 답을 찾으면 됩니다.

주어지는 수를 K라 하였을 때, 

입니다. 답을 찾기 위해 사용하는 연산의 수는 최대 44*44*44 = 85,184이며, 주어진 제한시간 1초를 충족하기에 충분합니다.

소스코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int triangleNum[45];

void initTriangleNum() {
	for (int i = 1; i < 45; i++) {
		triangleNum[i-1] = (i*i + i) / 2;
	}
}

bool isEurekaNumber(int K) {
	for (int a = 0; a < 44; a++) {
		for (int b = 0; b < 44; b++) {
			for (int c = 0; c < 44; c++) {
				if (triangleNum[a] + triangleNum[b] + triangleNum[c] == K) {
					return true;
				}
			}
		}
	}
	return false;
}
int main() {
	int T, K;
	
	cin >> T;
	initTriangleNum();
	
	for (int i = 0; i < T; i++) {
		cin >> K;
		if (isEurekaNumber(K))
			cout << 1 << endl;
		else
			cout << 0 << endl;
	}
	
	return 0;
}

main()함수에서 변수 T를 사용하여 test case의 개수를 입력 받고 initTriangleNum()함수를 사용하여 미리 필요한 양의 삼각수를 초기화합니다. 그리고 T의 크기 만큼 K를 입력받으면서 이 K가 Eureka number 인지 확인하기 위해 isEurekaNumber()함수로 확인하고 만약 true라면 1을, false라면 0을 출력하도록 하였습니다.

이상으로 글을 마치겠습니다.

감사합니다.