[백준] 2309번 일곱난장이 - Java(브루트포스)

[백준] 2309번 일곱난장이 - Java

 

문제 출처

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

2309번: 일곱 난쟁이

 

---

※ 풀이

전형적으로 브루트포스로 가능한 경우의 수를 다 해보면 되는 문제이다.

 

가능한 경우의 수를 계산을 해보았을 때 9명의 난쟁이 후보들이 있고 각각 난쟁이일 경우, 아닐경우 경우의 수가 있으니 2^9 정도라고 예상을 해볼 수 있다. 이는 제한시간이 2초임을 감안했을 때 충분히 풀 수 있는 시간이다.

(1초에 약 1억번의 연산이 가능하다고 생각하면 된다)

 

마지막에 키를 오름차순으로 출력하라고 하였으니 java sort 를 이용하여 정렬 후 출력하였다.

 

---

※ 소스코드

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

public class Main {

    static int[] arr = new int[9];

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

        //input
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        boolean isFinish=false;
        int sum = Arrays.stream(arr).sum();
        for (int i = 0; i < arr.length; i++) {
            for(int j=1;j<arr.length;j++){
                int temp = sum - arr[i] - arr[j];
                if (temp == 100) {
                    arr[i] = 1000;
                    arr[j] = 1000;
                    isFinish = true;
                    break;
                }
            }

            if(isFinish) break;
        }

        Arrays.sort(arr);
        Arrays.stream(arr).filter(s->s<1000).forEach(s->System.out.println(s));
    }
}

---