[Baekjoon] 2309번: 일곱 난쟁이

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

2309번: 일곱 난쟁이

문제 설명

아홉 명의 난쟁이들 중 스파이 난쟁이 2명이 숨어있다. 진짜 일곱 난쟁이들의 키의 합은 100이다. 아홉 난쟁이들 중 진짜 일곱 난쟁이들만 찾아내 그 키를 출력한다.

풀이 방법 1. 7중 반복문

제일 단순무식한 방법이다. 반복문을 이렇게 극단적으로 많이 써본 것도 처음이다.

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

class Main {

    final static int numOfDwarfs = 9;
    static int[] dwarfs = new int[numOfDwarfs];

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

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

        Arrays.sort(dwarfs);
        for (int a = 0; a < numOfDwarfs; a++) {
            for (int b = a + 1; b < numOfDwarfs; b++) {
                for (int c = b + 1; c < numOfDwarfs; c++) {
                    for (int d = c + 1; d < numOfDwarfs; d++) {
                        for (int e = d + 1; e < numOfDwarfs; e++) {
                            for (int f = e + 1; f < numOfDwarfs; f++) {
                                for (int g = f + 1; g < numOfDwarfs; g++) {
                                    int sum = dwarfs[a] + dwarfs[b] + dwarfs[c] + dwarfs[d] + dwarfs[e]
                                            + dwarfs[f] + dwarfs[g];
                                    if (sum == 100) {
                                        StringBuilder sb = new StringBuilder();
                                        sb.append(dwarfs[a]).append("\n");
                                        sb.append(dwarfs[b]).append("\n");
                                        sb.append(dwarfs[c]).append("\n");
                                        sb.append(dwarfs[d]).append("\n");
                                        sb.append(dwarfs[e]).append("\n");
                                        sb.append(dwarfs[f]).append("\n");
                                        sb.append(dwarfs[g]);
                                        System.out.println(sb);
                                        return;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

풀이 방법 1 제출 결과

풀이 방법 2. 총합에서 빼가면서 탐색하기

풀이 방법 1은 모든 요소를 더하는 방식으로 탐색했다면 이 방법은 모든 요소의 합에서 빼가는 방식으로 탐색한다. 풀이 방법 1처럼 더해가려면 7명의 난쟁이들을 모두 따져야 하지만 역으로 빼가는 방식으로 한다면 2명의 스파이 난쟁이만 찾아내면 되므로 훨씬 수월하게 찾아낼 수 있다.

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

class Main {

    final static int numOfDwarfs = 9;
    static int[] dwarfs = new int[numOfDwarfs];

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

        int sum = 0;
        for (int i = 0; i < numOfDwarfs; i++) {
            dwarfs[i] = Integer.parseInt(br.readLine());
            // 미리 모든 난쟁이들의 키를 더한다.
            sum += dwarfs[i];
        }

        for (int i = 0; i < 8; i++) {
            for (int j = i + 1; j < numOfDwarfs; j++) {
                // 두 난쟁이를 선택해서 키의 총합에서 뺀 값이 100이면 해당 난쟁이들이 스파이다.
                if (sum - dwarfs[i] - dwarfs[j] == 100) {
                    // 스파이를 처단한다.
                    dwarfs[i] = 0;
                    dwarfs[j] = 0;
                    
                    // 진짜 일곱 난쟁이들을 정렬시킨다.
                    Arrays.sort(dwarfs);
                    StringBuilder sb = new StringBuilder();
                    // 살아남은 진짜 일곱 난쟁이들의 키를 출력한다.
                    for (int k = 2; k < numOfDwarfs; k++)
                        sb.append(dwarfs[k]).append("\n");
                    System.out.print(sb);
                    return;
                }
            }
        }
    }
}

풀이 방법 2 제출 결과