JAVA 백준 10448 유레카 이론 (브루트 포스)

 

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

---

문제

1. 첫째 줄부터 테스트 케이스 T 가 주어진다.
2. 둘째 줄부터 T개의 각 줄에 자연수 K ( 3 <= K <= 1000 ) 가 주어진다.
3. 각 자연수 ( 1 <= n )에 대해 삼각수는 n ( n + 1 ) / 2 공식을 가진다.
4. 주어진 T개의 자연수 K가 3개의 삼각수의 합으로 표현될 수 있다면 1을, 그렇지 않다면 0을 출력한다.

---

 

 

정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        int[] list = new int[T];
        int[] sum = new int[1001];
        boolean[] result = new boolean[1001];

        int max = 0;

        for (int i = 0; i < T; i++) {
            int K = Integer.parseInt(br.readLine());
            list[i] = K;
            max = Math.max(max, list[i]);
        }

        int num = 0;

        for (int j = 1; j < max; j++) {
            sum[j] = j * (j + 1) / 2;

            if (sum[j] >= max) {
                num = j;
                break;
            }
        }

        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= num; j++) {
                for (int k = 1; k <= num; k++) {
                    int temp = sum[i] + sum[j] + sum[k];
                    if (temp <= 1000) {
                        result[temp] = true;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            if (result[list[i]]) {
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }

        System.out.println(sb);
    }
}

 

각 배열들은 크기를 넉넉하게 설정하였지만 전부 사용하지는 않는다.

삼각수가 주어진 자연수만큼 크다면 그만큼만 설정하도록 하였다.

 

그리고 boolean 배열을 이용하여 세 개의 삼각수의 합을 index라고 할 때 boolean[index]를 참으로 만들어 여러 번 계산하지 않도록 한다.

 

이후 자연수 K가 삼각수 3개의 합으로 만들어질 수 있는 수인지 확인하기 위해 boolean배열의 K 인덱스를 확인하여 0 또는 1을 출력할 수 있도록 한다.