2309번 : 일곱난쟁이

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처

2309번: 일곱 난쟁이

[문제 설명]

kks님 블로그에서 처음 본 완전탐색 문제.

총 인원이 9명밖에 되지 않기 때문에 완전탐색으로도 충분히 풀릴 문제다.

시간복잡도는 9명중에 2명을 택하는 9C2 = 36일듯하다. 

 

[처음 생각한 접근 방법]

완전탐색이므로 무지성 for문 돌렸다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        int[] dwarfHeights = new int[9];
        int sumOfHeights = 0;
        for (int i = 0; i < 9; i++) {
            dwarfHeights[i] = Integer.parseInt(bfr.readLine());
            sumOfHeights += dwarfHeights[i];
        }
        
        Arrays.sort(dwarfHeights);
        for (int i = 0; i < dwarfHeights.length-1; i++) {
            for (int j = i+1; j < dwarfHeights.length; j++) {
                if (sumOfHeights - dwarfHeights[i] - dwarfHeights[j] == 100) {
                    for (int k = 0; k < dwarfHeights.length; k++) {
                        if (k == i || k == j) continue;
                        System.out.println(dwarfHeights[k]);
                    }
                    return;
                }
            }
        }

        System.out.println(Arrays.toString(dwarfHeights));
    }
}