[Baekjoon] 2309 - 일곱 난쟁이

📝 문제

 

 

 

🔑 풀이 과정

① (순서없이) 9명중 7명을 뽑는 경우의 수 = 9명중 2명을 뽑는 경우의 수

만약 for문을 이용해 7명의 합을 더해 난쟁이 7명을 찾는것은 for문 7개를 사용해야 하므로 매우 복잡하다.

9명의 키의 합을 구한 뒤, 이중 for문을 사용해 두 명을 고른 뒤, 전체 키 합에서 두 명 키를 빼는 것이 더 효율적이다.

 

② 일곱 난쟁이의 키를 오름차순으로 출력해야 한다는 것. 입력을 받고 오름차순으로 정렬을 하자.

 

③ 첫 제출당시 틀렸습니다를 받고 질문게시판을 찾던중 발견한 글

여기서 2번을 내가 놓치고 있었다.

입력조건에서 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다고 되어있다.

첫 제출시 for문안에서 7명을 찾을 시 break를 하지 않아, 정답이 여러 가지일 경우 모두 출력하고 있었던 것

 

 

🔓 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] arr = new int[9];

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

        Arrays.sort(arr);

        int spy1 = 0;
        int spy2 = 0;
        loop:
        for(int i = 0; i < 8; i++){
            for(int j = i+1; j < 9; j++){
                if((sum - arr[i] - arr[j]) == 100){
                    spy1 = i;
                    spy2 = j;
                    break loop;
                }
            }
        }

        for(int i = 0; i < 9; i++){
            if((i == spy1) || (i == spy2))
                continue;
            else
                bw.write(arr[i] + "\n");
        }

        bw.flush();
        bw.close();

    }

}

 

 

 

🖤 알고리즘 분류

- 브루트포스 알고리즘

- 정렬