[백준] 2309번 : 일곱 난쟁이 (JAVA)

🔗 문제 링크

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

---

📌 문제 개요

9명의 난쟁이 키가 주어진다. 이 중 진짜 난쟁이 7명의 키 합은 100이다.

가짜 난쟁이 2명을 찾아 제외한 뒤, 진짜 난쟁이 7명의 키를 오름차순으로 출력해야 한다.

---

📌 접근 방법

전체 난쟁이 키 합을 먼저 구한다.

진짜 난쟁이 합이 100이므로 가짜 난쟁이 두 명의 키 합은 다음과 같다.

가짜 난쟁이 합 = 전체합 - 100

 

따라서 9명 중 2명을 선택하여
해당 두 명을 제외했을 때 합이 100이 되는 조합을 찾으면 된다.

 

이 문제는 경우의 수가 매우 작기 때문에
완전탐색(Brute Force) 으로 해결할 수 있다.

9명 중 2명 선택 → 9C2 = 36

 

---

📌 핵심 아이디어

전체 키 합 계산
↓
9명 중 두 명 선택 (이중 for문)
↓
sum - (a + b) == 100 확인
↓
조건 만족하면 두 명 제외
↓
나머지 7명 출력

 

또한 출력은 오름차순이어야 하므로
배열을 미리 정렬한 후 탐색을 진행한다.

---

📌 전체 코드

package no_2309;

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 fake1 = -1;
        int fake2 = -1;

        for(int a = 0; a < 8; a++){
            for(int b = a + 1; b < 9; b++){
                if(sum - (arr[a] + arr[b]) == 100){
                    fake1 = a;
                    fake2 = b;
                    break;
                }
            }
            if(fake1 != -1) break;
        }

        for(int i = 0; i < 9; i++){
            if(i != fake1 && i != fake2){
                System.out.println(arr[i]);
            }
        }
    }
}

---

📌 정리

이 문제는 완전탐색 기본 문제로 자주 등장하는 유형이다.

가짜 난쟁이 두 명의 키 합 = 전체합 - 100

 

9명 중 두 명을 선택하는 경우의 수는 36개뿐이므로
이중 반복문을 이용한 완전탐색으로 충분히 해결할 수 있다.

 

또한 출력 조건이 오름차순이기 때문에
탐색 전에 배열을 정렬하는 것이 중요하다.