백준 10448번: 유레카 이론 [완전탐색][브루트포스] -Java

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

10448번: 유레카 이론

K의 값이 1000보다 작기때문에 완탐을 시도할 수 있다.

시간 복잡도는 O(44^3) 

1000보다 작은 삼각수의 개수가 44개임

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		
		
		
		//입력 받기
		int TC = Integer.parseInt(st.nextToken());
		
		// Test case 반복
		for (int tc = 0; tc < TC; tc++) {
			st = new StringTokenizer(br.readLine());
			
			int K = Integer.parseInt(st.nextToken()); // K <= 1000
			int result = 0;
			
			//1. 모든 삼각수 구하기
			int triArr[] =new int[100]; //삼각수 N과 value를 담을 배열
			
			int N = 1;
			while(true) {
				int val = (N*(N+1))/2;
				if(val>1000) //K보다 작은 수들로 이루어져야하니 조건추가
					break;
				triArr[N] = val;
//				System.out.println("N = "+N+","+triArr[N]);
				N++;
			}
			
			//2. K로 삼각수 만들 수 있는지 각각 더해보기
			for (int i = 1; i < N; i++) {
				if(result==1)
					break;
				for (int j = 1; j < N; j++) {
					if(result==1)
						break;
					for (int l = 1; l < N; l++) {
						int sum = triArr[i]+triArr[j]+triArr[l];
						if(sum == K) {
//							System.out.println(sum);
//							System.out.println("i = "+i+",j = "+j+",l = "+l);
							result=1;
							break;
						}
							
					}
				}
			}
			System.out.println(result);
			
		}
		
		
	}

}