[백준] 2309 일곱 난쟁이 - Java(자바)

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

2309번: 일곱 난쟁이

 

문제 설명

---

 

풀이 과정

해당 문제는 브루트 포스를 이용하여 풀어야 한다. 그 전에 브루트 포스가 무엇인지 설명해보려고 한다.

 

브루트 포스란?

쉽게 말해서 모든 경우의 수를 탐색하여 요구조건에 해당하는 결과를 가져오는 것이다. 이 의미는 구현하기 쉽지만 모든 경우의 수를 탐색하기 때문에 결국 실행 시간이 오래 걸린다는 치명적인 단점이 있다.

핸드폰 잠금 방식 중에 4자리나 6자리 숫자로 된 핀번호를 입력하는 방식이 있는데, 이걸 시간 복잡도로 표현한다면 O(n^4, n^6)이 된다.

하지만 이 문제는 9개의 보기만 있기 때문에 이 방법을 이용하여 풀려고 한다.

 

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        int sum = 0;
        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 9; i++) {
            list.add(sc.nextInt());
            sum += list.get(i);
        }

        sc.close();

        for (int i = 0; i < 8; i++) {
            for (int j = i + 1; j < 9; j++) {
                if (sum - list.get(i) - list.get(j) == 100) {
                    list.remove(j);
                    list.remove(i);

                    Collections.sort(list);

                    for (int answer : list) {
                        System.out.println(answer);
                    }

                    return;
                }
            }
        }
    }
}

 

문제에 있는 예제 입력을 가지고 풀이를 해본다면 [20, 7, 23, 19, 10, 15, 25, 8, 13] 총 9개 숫자가 있다. 처음에 값을 입력받을때 sum을 구하고 sum은 140이 된다.

그리고 for문을 이용하여 모든 수를 반복하여 140 - 값1 - 값2 == 100이면 그 두 수를 배열에서 제거한 뒤, 배열을 정렬한 뒤 출력했다.