BOJ10448 유레카이론*

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

10448번: 유레카 이론

삼각합만 기록해둘 것이 아니라 합의 가능 유무도 기록해둔다면 테스트개수에 상관없이 답을 낼 수 있다.

어차피 완전탐색하면서 모든 값에 대한 가능성을 체크하기 때문에 사전작업을 모두 계산을 해놓는다면 시간복잡도가 일정하다.

 

또한 숫자 합을 하는 반복문을 여러개로 분리한다면 시간복잡도를 낮출 수 있다. 중간과정을 저장할 배열이 필요하다.

 

import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    int n = Integer.valueOf(br.readLine());
	    int[] tri = new int[50];
	    
	    for(int i =0; i<50; i++){
	        tri[i]= i*(i+1)/2;
	    }

	    
	    for(int i =0;i<n;i++){
	        find(Integer.valueOf(br.readLine()),tri,bw);
	    }
	    
		bw.flush();
		
		
		
		
	}
	
	public static void find(int num, int[] tri,BufferedWriter bw) throws IOException {
	    for(int i=1;i<50;i++){
	        for(int j=i;j<50;j++){
	            for(int k=j;k<50;k++){
	                if(tri[i]+tri[j]+tri[k]==num){
	                    bw.write("1\n");
	                    return;
	                }
	                if(tri[i]+tri[j]+tri[k]>num){
	                    break;
	                }
	            }
	        }
	    }
	    bw.write("0\n");
	}
	
	
	
}

class Main
{
    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;
            triangleNumbers[triangleNumberCount++] = triangleNumber;
        }

        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;
                    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");
        }
    }
}