[백준알고리즘] 브루트포스 - 2309번 일곱 난쟁이 문제

복습 차원으로, 그리고 빠르게 문제풀이를 진행하기 위해

본격적으로 브루트포스 문제들을 풀어보기 전 먼저 코드플러스 알고리즘 강의를 어느정도 듣고 나서 진행했다.

브루트포스는 모든 경우의 수들을 다 고려하는 무작정스러운 방법이기 때문에

문제를 풀기 전에 꼭!시간복잡도가 어느 정도 나올지 체크하고 이 방법을 택할 것인지 판단해야한다..
(실제 시험을 볼때는 문제 밑에 브루트포스라고 분류되어있진 않을테니..)

이 문제의 입력에서 주어질 입력은 늘 9개뿐이기 때문에 브루트포스로 해도 문제 없을 입력크기이다

게다가 가능한 정답이 여러개라면 그중 암거나 출력해도 된단다(해보다가 최초로 답을 찾았다면 반복문 중간에 나와도 괜찮음)

 

삼중 반복문으로 이루어졌고,

가짜 난쟁이라고 가정할 i,j번째 난쟁이를 제외한 나머지 난쟁이들의 키의 합이 100이 된다면

찐 난쟁이들만의 키를 출력하도록 했고

break를 두번 써서 완전히 반복문을 벗어나도록 했다

정렬은 미리 Arrays 클래스의 sort 함수를 이용하여 미리 정렬시켜놓았다

 

풀이코드

package baekjoonWeek3;

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

public class SevenDwarfs {   //백준 2309번 일곱난쟁이 문제
    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[] dwarfs = new int[9];  //9명의 난쟁이들 키
        for (int i = 0; i < 9; i++) {
            dwarfs[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(dwarfs);    //정렬부터

        int count = 0; int sum = 0;
        for (int i = 0; i < 9; i++) {
            if(sum == 100) break;   //완전 빠져나가기 위해 break 한번더써줌
            for (int j = i + 1; j < 9; j++) {
                sum = 0;
                for (int k = 0; k < 9; k++) {
                    if (k == i || k == j) {
                        continue;   //i,j번째는 가짜난쟁이로 일단 간주하므로 건너뜀
                    }
                    sum += dwarfs[k];
                }
                if (sum == 100) {
                    for (int h = 0; h < 9; h++) {
                        if (h == i || h == j) { //가짜난쟁이 빼고 출력
                            continue;
                        }
                        bw.write(Integer.toString(dwarfs[h]));
                        bw.newLine();
                    }
                    break;
                }
            }
        }
        bw.flush();
        bw.close();
    }
}