완전탐색 - 백준 (10448) 유레카 문제

 

 

- 풀이

import java.io.*;

public class Main{
    static boolean[] isEurekaNumber = new boolean[1001]; 
    public static void main(String[] args) throws IOException{
        int[] triangleNumber = new int[50];
        int triagleCnt = 0;
        for(int i =1;;i++){
         int number = i*(i+1)/2;
         if(number > 1000) break;
         triangleNumber[triagleCnt++] = number;
        }
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        preprocess();
        
        
        
        while(n -- > 0){
        
           int k = Integer.parseInt(br.readLine());
           boolean result = isEurekaNumber[k];
           if(result == true){
               System.out.println("1");
           }else{
               System.out.println("0");
           }
        
        }
    }
    
    private static void preprocess(){
                //3각수 구하기 
                int[] triangleNumber = new int[50];
                int triangleCnt = 0;
                for(int i =1;;i++){
                    int number = i*(i+1)/2;
                    if(number > 1000) break;
                    triangleNumber[triangleCnt++] = number;
                }
                boolean[] isSumOfTriangle = new boolean[1001];
                for(int i=0; i<triangleCnt; i++){
                    for(int j=0; j<triangleCnt; j++){
                        if(triangleNumber[i] + triangleNumber[j] <=1000)
                            isSumOfTriangle[triangleNumber[i] + triangleNumber[j]] = true;
                    }
                }
                for(int i=1; i<=1000;i++){
                    if(!isSumOfTriangle[i]) continue;
                    for(int j=0; j<triangleCnt; j++){
                        int eurekaNumber = i + triangleNumber[j];
                        if(eurekaNumber > 1000) break;
                        isEurekaNumber[eurekaNumber] = true;
                    }
                }
            }
    
}

 

 

- 얻은 것 

 

1. 완전 탐색을 구현할 때 위와 같이 미리 정해진 수가 있다면 미리 구해 둘 것 

  //3각수 구하기 
                int[] triangleNumber = new int[50];
                int triangleCnt = 0;
                for(int i =1;;i++){
                    int number = i*(i+1)/2;
                    if(number > 1000) break;
                    triangleNumber[triangleCnt++] = number;
                }

 

2. 길이가 미리 정해진 수의 합을 구할 때 쓸 수 있는 방법 

 

  boolean[] isSumOfTriangle = new boolean[1001];
                for(int i=0; i<triangleCnt; i++){
                    for(int j=0; j<triangleCnt; j++){
                        if(triangleNumber[i] + triangleNumber[j] <=1000)
                            isSumOfTriangle[triangleNumber[i] + triangleNumber[j]] = true;
                    }
                }
                for(int i=1; i<=1000;i++){
                    if(!isSumOfTriangle[i]) continue;
                    for(int j=0; j<triangleCnt; j++){
                        int eurekaNumber = i + triangleNumber[j];
                        if(eurekaNumber > 1000) break;
                        isEurekaNumber[eurekaNumber] = true;
                    }
                }

 

> 두 수의 합을 먼저 구해서 저장하고, 나머지 하나를 더해가며 저장

 

 

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

10448번: 유레카 이론