2309번: 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 아홉 명의 난쟁이가 찾아왔습니다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다. 뛰어난 수학 실력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈습니다. 아홉 난쟁이의 키가 주어졌을 때, 진짜 일곱 난쟁이를 찾는 문제입니다.

• 입력: 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어집니다. (1 이상 100 이하의 자연수)
• 출력: 일곱 난쟁이의 키를 오름차순으로 출력합니다. (정답이 여러 가지인 경우에는 아무거나 출력합니다.)

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

풀이 1: 가짜 난쟁이 2명 찾기 (이중 반복문)

9명 중 7명을 골라 합이 100이 되는 조합을 찾는 문제이지만, 발상을 전환하면 '9명 중 합에서 제외할 가짜 난쟁이 2명을 찾는 문제'로 풀 수 있습니다.

1. 총합 및 정렬: 먼저 9명 난쟁이 키의 총합(sum)을 구합니다. 문제에서 오름차순으로 출력할 것을 요구했으므로, 탐색을 시작하기 전에 미리 배열을 오름차순으로 정렬(Arrays.sort)해 둡니다.
2. 완전탐색 (이중 반복문): 이중 반복문을 사용하여 9명 중 2명(i, j)을 뽑는 모든 경우의 수를 확인합니다. 만약 전체 총합에서 i번째 난쟁이와 j번째 난쟁이의 키를 뺐을 때 딱 100이 된다면(sum - a[i] - a[j] == 100), 그 두 명이 바로 가짜 난쟁이입니다.
3. 출력 및 즉시 종료: 가짜 난쟁이를 찾았다면, 전체 난쟁이를 다시 순회하며 인덱스가 i 또는 j인 사람을 제외(continue)하고 나머지 7명의 키를 출력합니다. 정답이 여러 개일 수 있으나 하나만 출력해야 하므로, 출력을 마친 뒤에는 bw.flush()로 버퍼를 비우고 return을 호출하여 프로그램을 즉시 종료합니다.

코드 1

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

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[] a = new int[9];
       int sum = 0;

       // 1. 아홉 난쟁이의 키를 입력받으며 총합을 구함
       for (int i = 0; i < 9; i++) {
          a[i] = Integer.parseInt(br.readLine());
          sum += a[i];
       }

       // 2. 오름차순 출력을 위해 미리 배열 정렬
       Arrays.sort(a);

       // 3. 가짜 난쟁이 2명 찾기 (브루트포스)
       for (int i = 0; i < 8; i++) {
          for (int j = i + 1; j < 9; j++) {
             // 전체 합에서 두 명의 키를 뺐을 때 100이 된다면
             if (sum - a[i] - a[j] == 100) {

                // 가짜 난쟁이 2명(i, j)을 제외한 나머지 7명 출력
                for (int k = 0; k < 9; k++) {
                   if (k == i || k == j)
                      continue;
                   bw.write(a[k] + "\\n");
                }

                // 정답을 하나 찾았으므로 출력 후 프로그램 즉시 종료
                bw.flush();
                return;
             }
          }
       }
    }
}

풀이 2: 진짜 난쟁이 7명 찾기 (재귀 / 백트래킹)

발상의 전환 없이 문제의 요구사항 그대로 9명 중 7명을 뽑는 모든 조합(Combination)을 재귀를 통해 구하는 정석적인 방법입니다.

1. 정렬 및 탐색 시작: 미리 배열을 오름차순 정렬해 둔 뒤, 재귀 함수 go를 호출하여 7명의 조합을 만들어 나갑니다.
2. 백트래킹: 리스트에 난쟁이의 키를 추가(list.add)하여 다음 깊이로 넘어가고, 탐색이 끝나면 다시 리스트에서 제거(list.remove)하여 다른 경우의 수를 탐색할 수 있도록 원상 복구합니다.
3. 기저 조건 (종료 조건): 리스트의 크기가 7이 되면 7명이 모두 뽑힌 것이므로 합을 구합니다. 만약 합이 100이라면, 해당 리스트의 상태를 ans 변수에 깊은 복사(List.copyOf)하여 저장합니다.

코드 2

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

public class Main {
    static int[] a = new int[9];
    static List<Integer> ans;

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

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

       // 오름차순 출력을 위해 미리 배열 정렬
       Arrays.sort(a);

       // 조합 탐색 시작
       go(0, new ArrayList<>());

       // 탐색 완료 후 저장된 정답 리스트 출력
       for (int i : ans) {
          bw.write(i + "\\n");
       }

       bw.flush();
    }

    static void go(int idx, List<Integer> list) {
       // 정답을 이미 찾았다면 불필요한 추가 탐색을 방지하기 위한 최적화
       if (ans != null) return;

       // 7명이 모두 뽑혔을 때
       if (list.size() == 7) {
          int sum = 0;
          for (int i = 0; i < 7; i++) {
             sum += list.get(i);
          }

          // 합이 100이라면 정답으로 저장
          if (sum == 100) {
             ans = List.copyOf(list); // 현재 리스트 상태를 복사하여 불변 리스트로 저장
          }
          return;
       }

       // 9명 중 7명을 뽑는 백트래킹 로직
       for (int i = idx; i < 9; i++) {
          list.add(a[i]);
          go(i + 1, list);
          list.remove(list.size() - 1); // 다른 조합을 찾기 위한 원상 복구
       }
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 정렬 (Sorting), 백트래킹 (Backtracking)