[BruteForce] 백준 2309: 일곱 난쟁이

2309번: 일곱 난쟁이 (acmicpc.net)

2309번: 일곱 난쟁이

 

간만에 브론즈 문제.

 

내가 브루트포스 문제가 많이 약한데 그래도 쉽게 풀 수 있던 문제였다.

 

9명 중 7명을 고르는 경우의 수는 사실 택도 없이 작기 때문에, 브루트포스를 써도 될지 고민할 필요는 없었다.

 

먼저, 난쟁이들의 키를 저장하기 위한 배열 dwarf, 해당 난쟁이가 체크되었는지 확인하는 배열 isChecked를 만들었다.

 

    static int[] dwarfs = new int[9];
    static boolean[] isChecked = new boolean[9];

 

재귀함수를 통해서 완전탐색을 구현하였다.

 

재귀함수는 dwarf[], isChecked[] 배열, 현재까지 체크된 난쟁이의 수 num, 현재까지 체크된 난쟁이 키의 합 sumHeight, 체크를 시작할 인덱스인 idx를 매개변수로 받는다.

 

 static void addHeights(int[] dwarfs,boolean[] isChecked,int num,int sumHeight,int idx){}

체크한 난쟁이 수가 7명이 되면 무조건 return해 줘야 한다. 이 때, 조건문을 통해 난쟁이 키의 합이 100이면 정답 배열에 그 값을 넣어준다.

 

if(num==7){
    if(sumHeight==100){
        int answerIdx = 0;
        for(int i=0;i< isChecked.length;i++){
            if(isChecked[i]){
                answerSheet[answerIdx]=dwarfs[i];
                answerIdx++;
            }
        }
    }
    return;
}

 

만일 아직 체크한 난쟁이 수가 7인이 아니면, 탐색을 시작할 인덱스인 idx로부터 isChecked 배열을 순회하면서 아직 체크하지 않은 난쟁이를 만났을 때 해당 isChecked 값을 true로 만들고, 재귀함수를 호출해 주었다. 

 

재귀함수를 호출하고 난 후에는 다시 isChecked 값을 false로 원상 복귀시켜 주어야 한다. 안 그러면 순서대로 1234567 세어 보는 경우의 수만 파악하고 끝날 것이다.

 

for(int i=idx;i< isChecked.length;i++){
    if(!isChecked[i]){
        isChecked[i]=true;
        addHeights(dwarfs,isChecked,num+1,sumHeight+dwarfs[i],i);
        isChecked[i]=false;
    }
}

 

이후에는 정답 배열(answerSheet)을 순서대로 정렬해서 출력만 해주면 끝이다. 전체 코드 첨부하고 마친다.

import java.io.*;

public class BOJ_2309 {
    static int[] dwarfs = new int[9];
    static boolean[] isChecked = new boolean[9];
    static int[] answerSheet = new int[7];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        addHeights(dwarfs,isChecked,0,0,0);
        sortAnswer();
        for(int i=0;i< answerSheet.length;i++){
            System.out.println(answerSheet[i]);
        }
    }

    static void addHeights(int[] dwarfs,boolean[] isChecked,int num,int sumHeight,int idx){
        if(num==7){
            if(sumHeight==100){
                int answerIdx = 0;
                for(int i=0;i< isChecked.length;i++){
                    if(isChecked[i]){
                        answerSheet[answerIdx]=dwarfs[i];
                        answerIdx++;
                    }
                }
            }
            return;
        }

        for(int i=idx;i< isChecked.length;i++){
            if(!isChecked[i]){
                isChecked[i]=true;
                addHeights(dwarfs,isChecked,num+1,sumHeight+dwarfs[i],i);
                isChecked[i]=false;
            }
        }
    }

    static void sortAnswer(){
        for(int i=0;i<answerSheet.length-1;i++){
            for(int j=i+1;j< answerSheet.length;j++){
                if(answerSheet[j]<answerSheet[i]){
                    int tmp = answerSheet[j];
                    answerSheet[j]=answerSheet[i];
                    answerSheet[i]=tmp;
                }
            }
        }
    }
}