[백준 10448번] 유레카 이론

문제

번호

백준 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을 출력한다.

 

입출력

입력	출력
3 10 20 1000	1 0 1

 

언어

JAVA

 

---

풀이

무조건 3개의 삼각형의 합으로 구성 가능한지 확인하는 문제이다.

때문에 3개의 자연수 i, j, k로 구성되어있는지 확인하면 된다.

 

$T_i + T_j + T_k$로 이루어진 숫자는

이므로, 계산의 속도를 높이기 위해서 다음과 같이 확인하면 된다.

 

아래 코드를 보면 반복문의 시작 조건이 각각 <pre>i = 1</pre>, <pre>j = i</pre>, <pre>k = j</pre>로 되어있다.

만약 <pre>i = 1</pre>, <pre>j = 1</pre>, <pre>k = 1</pre>로 둔다면 계산의 중복이 일어난다.

결과가 같음에도 불구하고 $T_1 + T_2 + T_3$와 $T_2 + T_1 + T_3$가 일어난다는 말이다.

따라서 계산의 횟수를 줄이기 위해서 시작 조건을 이처럼 설정하였다.

 

---

코드

import java.util.Scanner;

public class Main {

    public static int searchTriangle(int num) {
        int max = (int)(num/2) + 1;

        // 3개의 삼각형으로 이루어졌는지 확인하기 위해서 i = 1 부터 시작
        for(int i = 1 ; i < max ; i++) {
            for(int j = i ; j < max ; j++) {
                for(int k = j ; k < max ; k++) {
                    if((i*(i+1) + j*(j+1) + k*(k+1)) == 2*num) {
                        return 1;
                    }
                }
            }
        }

        // 불가능한 경우
        return 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int cnt = scanner.nextInt();
        for(int i = 0 ; i < cnt ; i++) {
            scanner.nextLine();
            int answer = searchTriangle(scanner.nextInt());
            System.out.println(answer);
        }

        scanner.close();
    }
}