[JAVA] 백준 10448번 : 유레카 이론

 

문제

삼각수 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은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

 

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

 

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다. ( k = 삼각수의 합 )

 

예제 입력

3
10
20
1000

 

예제 출력

1
0
1

 

 

문제 접근하기

 

1. 1000을 사용하여 배열의 크기가 45인 배열 만들기

    - i * ( i + 1 ) / 2 = 1000 , 따라서 i  < 45

 

2. 삼각수를 만드는 함수 만들기(eureke 함수)

 

3. 3중 for문으로, 3개의 삼각수를 더한 값과 입력한 값을 비교하여, 같으면 1, 다르면 0을 출력

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
        
		//자연수의 범위가 3 <= N <= 1000
		int [] triArr = new int[45]; // 배열의 크기 45 ( i*(i+1)/2 = 1000 )
		
		// 1 ~ 44까지의 삼각수 구하기
		for (int i = 1; i < 45; i++) {
			triArr[i] = i * (i + 1) / 2;
		}
		
		for (int i = 0; i < num ; i++) {
			int n = Integer.parseInt(br.readLine());
			int result = eureka(n, triArr);
			
			System.out.println(result);
		}		
	}	
	
	
	public static int eureka(int num, int[] triArr) {
		for (int i = 1; i < 45; i++) {
			for (int j = 1; j < 45; j++) {
				for (int k = 1; k < 45; k++) {
					
					int sum = triArr[i] + triArr[j] + triArr[k]; // 삼각수 3개의 합
					
					if( sum == num ) {
						return 1;
					}
				}
			}
		}
		return 0;		
	}
}