[BOJ] 10448 유레카 이론

유레카 이론

풀이

• Tn = 1+2+3+...+n = n(n+1)/2 라는 공식이 있고, 정수가 주어졌을 때 정확히 3개의 삼각수의 합으로 표현될 수 있는지를 구해야 한다.
• K의 범위가 3<=K<=1,000 이므로, 1,000까지의 삼각수를 일단 다 구해놓고, 주어지는 k보다 작은 Tn이 어딘지 찾아놨다.(end 변수에 저장)
• 그리고 3중 for문을 찾아놓은 end까지 돌리면서, 세 개의 수 합해서 K가 나오면 true, 아니면 false를 반환하게 구현했다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] tarr = new int[45];
        for(int i=0;i<45;i++){
            tarr[i] = i*(i+1)/2;
        }
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(br.readLine());
            int end = -1;
            for(int k=0;k<tarr.length;k++){
                if(tarr[k]>num){
                    end = k-1;
                    break;
                }
            }
            if(end==-1) end = tarr.length-1;
            boolean find = false;
            L:for(int k=1;k<=end;k++){
                int first = tarr[k];
                for(int m=k;m<=end;m++){
                    int sec = tarr[m];
                    for(int n=m;n<=end;n++){
                        int third = tarr[n];
                        if(first+sec+third==num){
                            System.out.println(1);
                            find = true;   //찾은 경우
                            break L;
                        }
                    }
                }
            }
            if(!find) System.out.println(0);
        }
    }
}