[백준] 유레카 이론

유레카 이론 해결

가우스가 증명한 바와 같이, 모든 자연수는 최대 3개의 삼각수의 합으로 표현될 수 있습니다. 이 코드는 주어진 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지를 판단합니다.

문제 조건

• 시간 제한: 1초
• 메모리 제한: 256MB
• 제출: 15432
• 정답: 9002
• 맞힌 사람: 7036
• 정답 비율: 57.470%
• 문제 링크

10448번: 유레카 이론

입력

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

출력

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

주요 개념

• 삼각수의 계산: 삼각수는 n(n+1)/2 공식을 통해 계산됩니다.
• 유레카 수 판별: 주어진 숫자가 3개의 삼각수의 합으로 나타낼 수 있는지 미리 계산하여 저장합니다.

코드 설명

static boolean[] isEurekaNumber = new boolean[1001]; // 유레카 수를 저장할 배열

public static void preprocess() {
    int[] triangleNumbers = new int[50]; // 삼각수를 저장할 배열
    int triangleNumberCount = 0; // 삼각수의 개수
    // 삼각수 계산
    for (int i = 1; ; i++) {
        int triangleNumber = i * (i + 1) / 2;
        if (triangleNumber > 1000) break; // 1000을 초과하는 삼각수는 계산하지 않음
        triangleNumbers[triangleNumberCount++] = triangleNumber; // 삼각수 저장
    }

    // 삼각수 3개의 합으로 표현될 수 있는 수 계산
    for (int i = 0; i < triangleNumberCount; i++)
        for (int j = i; j < triangleNumberCount; j++)
            for (int k = j; k < triangleNumberCount; k++) {
                int eurekaNumber = triangleNumbers[i] + triangleNumbers[j] + triangleNumbers[k];
                if (eurekaNumber > 1000) break; // 1000을 초과하는 수는 계산하지 않음
                isEurekaNumber[eurekaNumber] = true; // 유레카 수로 저장
            }
}

public static void main (String[] args) {
    preprocess(); // 유레카 수 계산

    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt(); // 테스트케이스 수 입력
    while (T-- > 0) {
        int K = sc.nextInt(); // 검사할 수 입력
        // 유레카 수 판별 결과 출력
        System.out.println(isEurekaNumber[K] ? "1" : "0");
    }
}