백준 :: 완전탐색

 

문제집: 너무 어렵지 않은 완전 탐색 (ilyoan)

 

 

---

일곱 난쟁이

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] height = new int[9];
        int sum = 0;

        for(int i = 0; i < 9; i++){
            height[i] = Integer.parseInt(br.readLine()) ;
            sum += height[i];
        }

        // 다 더해서 빼는 방식으로..!
        for(int i = 0; i < 8; i ++){
            for(int j = i+1; j < 9; j++){
                if(sum - height[i]- height[j] == 100){
                    height[i] = 0;
                    height[j] = 0;

                    Arrays.sort(height);
                    for(int k = 2; k <9; k++){
                        System.out.println(height[k]);
                    }
                    return;
                }
            }
        }

    }
}

 

 

 

 

 

---

유레카 이론

 

 

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

       

        for (int i = 0; i < N; i++){

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

            System.out.println(dfs(K)? 1: 0);

        }

       

    }

    public static Boolean dfs(int K){

        int length = 45; // 1000이 max이므로 44까지만 가능

        for(int i = 1; i < length; i++){

            int calculate1 = i*(i+1)/2;

            if(calculate1 > K) break;

           

            for(int j = 1; j < length; j++){

                int calculate2 = j*(j+1)/2;

                if(calculate2 > K) break;

                for(int l = 1; l < length; l++){

                    int calculate3 = l*(l+1)/2;

                    if(calculate3 > K) break;

                    if(calculate1 + calculate2 + calculate3 == K) return true;

                }

            }

        }

        return false;

    }

}