[BOJ2309] 일곱 난쟁이

백준 2309 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

---

브루트포스의 기본적인 문제라 보면 되겠다.

브루트포스란?

브루트 (Brute) + 포스 (Force) => 짐승의 힘 => 무식한 힘!

무식하게 모든 것을 다 탐색한다는 것이다. 그래서 완전 탐색이라고 한다.

 

그럼 이 문제가 왜 브루트포스인가?

9명의 난쟁이들 중 7명을 골라야 하는데, 다 합해서 100이 되는지는 하나씩 모두 더해봐야 아는 것이기 때문이다.

그렇다면 7번을 반복..? 말이 안된다.

 

7, 8, 10, 13, 15 ... 써서 7개씩 묶어보면 되긴 하지만, 잘 생각해보면 9명 중 2명만 빼면 되는 것을 알 수 있다.

즉, 우리는 9명의 난쟁이 키를 모두 더한 것에서 2명의 키를 뺐을 때 100이 나오기만 하면 되는 것이다.

7개를 더하는것 보단, a - 2명 == 100 이 낫지 않을까.

 

이중 for문으로 arr[i], arr[j]를 뺐을 때 100이 나오면 끝난 것이다.

i 와 j 가 배열의 모든 부분을 탐색하면서 끌어낸 결과이다.

 

작년에 왜 세번이나 틀렸는지 하나씩 열어봤는데..

반복문이라는 걸 제대로 쓸 줄을 몰랐나? 너무 부끄러워 그냥 닫아버렸다.

아마도 다른 분의 코드를 참고해서 쓴 듯하다..ㅎ

 

시간을 줄일 수 있었던 것은 아마도 StringBuilder를 사용해서인 것 같다. 

작년 당시에는 BufferWriter로 바로 바로 출력했는데..

아니라면 누구든 알려주세요!😆 

 

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ2309 {
    private static int[] arr;
    private static int sum = 0, a, b;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        arr = new int[9];

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

        search();
        for(int i = 0; i < 9; i++){
            if(i == a || i == b){
                continue;
            }else{
                sb.append(arr[i] + "\n");
            }
        }
        System.out.println(sb);
    }
    private static void search(){
        for(int i = 0; i < 9; i++){
            for(int j = 1; j < 9; j++){
                if(sum - (arr[i] + arr[j]) == 100) {
                    sum -= (arr[i] + arr[j]);
                    a = i; b = j;
                    return;
                }
            }
        }
    }
}