BOJ 10448 유레카 이론

문제출처 : https://www.acmicpc.net/problem/10448

1. 문제요약

- Tn = n(n+1)/2

- 자연수 K가 주어졌을 때 세개의 Tn 으로 나타낼 수 있으면 1, 없으면 0

- 3 <= K <= 1,000

2. 접근방법

- Tn이 몇개나 필요할까? => n(n+1)/2 <= 1,000 을 만족하는 n은 대충 44, 45

- T1 ~ T45 까지 3개를 뽑으면 되므로 45 * 45 * 45 = 91,125 이므로 1초 내에 들어옴

- 즉, 브루트 포스

- 여기서 45 * 45 * 45는 중복이 포함

- T1 + T1 + T2 / T1 + T2 + T1 / T2 + T1 + T1 은 같은 경우 이므로 제외 하면 조금 더 빨라 지겠지?

※ 실제로 다 해본 경우는 32ms / 중복 제외한 경우는 28ms

3. 시간복잡도

- N^3 = 91,125

4. 회고

- 미리 결과 합을 구해두면 출력에 편함

- 어차피 시간내에 들어오므로 굳이 안해도 됨

- 미리 구한 다른 사람은 0ms 인데 난 왜 28ms 이냐!!!

- 싱크 안맞춘 cin 때문인가.... T의 갯수가 몇개인지 모르니

- 미리 세개의 합을 구한 배열을 지역변수에서는 T45 + T45 + T45 = 3105 이상으로 잡아야 오버 인덱스 안남

  전역변수로 선언한다면 100 개 정도는 더 잡아주는 거 같음 3000개로도 통과되네

소스코드

#include<iostream>
using namespace std;

int main(void){
	int t, E[46] = { 0, 1 }, C[4000] = { 0 };
	cin >> t;

	for (int i = 2; i < 46; i++) E[i] = E[i - 1] + i;
	for (int i = 1; i < 46; i++)
		for (int j = i; j < 46; j++)
			for (int k = j; k < 46; k++)
				C[E[i] + E[j] + E[k]] = 1;

	while (t--){
		int n;
		cin >> n;
		cout << C[n] << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]