02.05. 유레카 이론[Brute-force Search][백준 10448]

https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

 

Algorithm classification : Brute-force Search, Math

 

02.05.1. Problem

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

[그림]

자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1 + T2
• 5 = T1 + T1 + T2
• 6 = T2 + T2 or 6 = T3
• 10 = T1 + T2 + T3 or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

Given a natural number, write a program to determine whether the integer can be expressed as the sum of exactly three triangular numbers. However, it is not necessary for all three triangular numbers to be different.

 

02.05.2. Input limit

The program uses standard input. The number of test cases is given in the first line of the input. Each test case is composed of T lines with one natural number K (3 ≤ K ≤ 1,000) per line.

 

02.05.3. Output

The program uses standard output. Print exactly one line for each test case. Outputs 1 if K can be expressed as the sum of exactly three triangular numbers, and 0 otherwise.

 

02.05.4. Solution

K의 최대값이 1,000이므로 1,000이하의 삼각수를 3중 for문으로 돌려서 K가 되는 경우가 있는지 찾으면 됩니다. 이때 삼각수는 미리 구해 놓으면 도움이 되겠죠. 그리고 굳이 1,000까지 다 구할 필요없이 적당한 숫자이하의 삼각수만 미리 구해놓으면 됩니다.

	for(i = 0; i < n; i++){
		scanf("%d", &data[i]);
		max0 = max(max0, data[i]);
	}
	int t[max0];
	for(i = 1; i < (int)sqrt(max0 * 2) + 1; i++){
		t[i] = (i*i + i)/2;
	}

	for(i = 0; i < n; i++){
		for(j = 1; j < data[i]; j++){
			for(k = 1; k < data[i]; k++){
				for(r = 1; r < data[i]; r++){
					if(data[i] == t[j] + t[k] + t[r]){
						//printf("%d %d %d %d\n",data[i], t[j], t[k], t[r]);
						data[i] = 0;
					}
				}
			}
		}
        printf("%d\n", data[i] ? 0 : 1);
	}