백준 2309번 일곱 난쟁이 완전탐색(brute-force) 알고리즘 문제 :: 코드 자몽

완전 탐색 Brute-Force

완전 탐색은 말 그대로 모든 경우의수를 일일이 탐색하여 정답을 찾아내는 알고리즘이다. 가능한 방법을 모두 확인하여 정확도가 높고 강력한 방식이지만, 시간은 다소 오래 걸리는 단점이 있습니다. 그래서 브루트 포스 알고리즘을 사용하기 전에 문제의 가능한 경우의 수를 먼저 계산을 해봐야한다. 컴퓨터가 1초에 대략 1억 번 정도의 일을 할 수 있다고 한다. 효율성을 고려하여 브루트 포스 알고리즘으로 문제를 접근할 경우 기준은 정해주는 것이 좋다. 예를 들어 "천만(10,000,000) 건 이하의 경우 수가 존재할 때만 브루트 포트 알고리즘을 사용하겠다."라는 기준을 정하고 문제를 접근하는 것이 유리하다.

 

 

[백준] 2309번 일곱 난쟁이

2309번: 일곱 난쟁이

 

풀이

9명중 7명의 키를 합산하여 100의 값이 나오는 경우를 찾는 것이 목표이다. 9C7을 변환하여 9C2로 계산을 해보면 총 (9*8)/(2*1) = 36가지 경우의 수가 나온다. 해당 문제는 브루트 포스 알고리즘을 사용하여 풀기에 적합하다.

 

Java

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        int totalSum = 0;
        while (sc.hasNext()){
            int num = sc.nextInt();
            totalSum += num;
            list.add(num);
        }
        Collections.sort(list);
 
        outerLoop : for(int i=0; i<list.size()-1; i++){
            for(int j=i+1; j<list.size(); j++){
                if(totalSum - list.get(i) - list.get(j) == 100){
                    for(int k=0; k<list.size(); k++){
                        if(k != i && k != j){
                            System.out.println(list.get(k));
                        }
                    }
                    break outerLoop;
                }
            }
        }
    }
}