백준 10448. 유레카 이론

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

단순 구현문제에서 규칙을 찾으려고 머리 싸맸던 문제
입력으로 주어진 자연수의 범위가 3<=N<=1000이었기 때문에 단순 구현을 하여도 시간초과가 나지 않는 문제였다.

자연수의 가장 큰 값이 1000이라는 것은 n*(n+1)/2 가 최대 1000까지 나온다는 말이고, 이때 n은 최대 44가 된다.

그래서 그냥 45칸의 배열을 만들고 거기에 삼각수 값을 넣은 후 3번의 for문을 돌리면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Boj_10448 {
    static int[] triNum = new int[45];

    public static void triangular_number(){
        for(int i=1; i<45; i++){
            triNum[i] = i*(i+1)/2;
        }
    }

    public static boolean eureka(int N){
        for(int a=1; a<45; a++){
            for(int b=1; b<45; b++){
                for(int c=1; c<45; c++){
                    if(triNum[a]+triNum[b]+triNum[c]==N) return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        triangular_number();

        for(int t=0; t<T; t++){
            int N = Integer.parseInt(br.readLine());

            if(eureka(N)) bw.write("1");
            else bw.write("0");

            bw.write("\n");
        }
        bw.flush();
    }
}