알고리즘 풀이 - 백준 2309(일곱 난쟁이, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

9명의 난쟁이의 키가 주어졌을 때, 합이 100이 되는 7명의 난쟁이의 키를 오름차순으로 출력하는 문제

 

 

2. 풀이

 

우선 간단히 경우의 수를 생각해보자. 9명의 난쟁이 중 7명의 경우 키가 합이 100이 되므로 우리는 7명을 찾는 것이 아니라 2명을 걸러내는 것이 더 효율적이다.

즉, 전체 경우의 수는 아홉 중 둘을 골라내므로 ${}_{9}C_{2}$의 경우가 되어 총 36가지의 경우의 수가 있다.

 

따라서, 이 문제는 완전탐색으로 풀어도 큰 문제가 없다.

 

풀이는 다음과 같다.

① 우선 전체 난쟁이의 키를 더하고 배열을 정렬한다.
② 전체 키를 더한 값에서 100을 뺀 값과 특정 난쟁이 2명의 키가 같다면 해당 두 난쟁이는 제외하면 된다.

 

모든 가능한 경우를 출력하는 것이 아니므로 출력이 끝나면 도중에 반복문을 모두 빠져나오는 코드를 잊지 말아야 한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

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 d[] = new int[9];
        
        // 난쟁이들 키 미리 모두 더한 것에 -100을 수행
        int sum = -100;
        for(int i=0; i < 9; i++){
            d[i] = Integer.parseInt(br.readLine());
            sum += d[i];
        }
        
        // 해당 배열을 정렬 수행
        // 퀵 정렬 직접 구현함
        quickSort(d);
        print(d, sum, bw);
        
        bw.flush();
        br.close();
    }
    
    private static void print(int[] d, int sum, BufferedWriter bw) throws IOException{
        // 반복문 돌면서 출력 수행
        for(int i=0; i < d.length; i++){
            for(int j=i; j < d.length; j++){
            
                // 만약 i, j번째의 합이 현재 sum과 같다면 해당 2개를 제외한 나머지의 합이 100임
                if(d[i] + d[j] == sum){
                    // i, j번째를 제외하고 모두 출력
                    for(int k=0; k < d.length; k++){
                        if(k != i && k != j){
                            bw.write(d[k] + "\n");
                        }
                    }
                    return;
                }
            }
        }
    }
    
    // 아래는 퀵 정렬 수행하는 부분
    private static void quickSort(int[] d){
        quickSort(d, 0, d.length);
    }
    
    private static void quickSort(int[] d, int start, int end){
        if(end - start < 2){
            return;
        }
        
        int pivot = partition(d, start, end);
        quickSort(d, start, pivot);
        quickSort(d, pivot+1, end);
    }
    
    private static int partition(int[] d, int start, int end){
        int pivot = d[start];
        int i = start;
        int j = end;
        
        while(i < j){
            while(i < j && d[--j] >= pivot);
            while(i < j && d[++i] <= pivot);
            
            if(i < j){
                swap(d, i, j);
            }
        }
        
        swap(d, start, j);
        return j;
    }
    private static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.