[백준] 2309

백준 2309번 문제 풀이: 일곱 난쟁이

이번 포스팅에서는 백준 2309번 문제인 "일곱 난쟁이"를 자바로 해결한 방법을 공유하고자 합니다. 문제 해결을 위해 사용된 알고리즘과 코드의 흐름을 차근차근 설명하겠습니다.

문제 개요

이 문제는 총 9명의 난쟁이 중에서 7명의 키의 합이 100이 되도록 하는 난쟁이들을 찾아내는 문제입니다. 이를 위해 우리는 9명의 난쟁이 키에서 임의의 2명을 제외한 7명의 키를 선택하여 그 합이 100이 되는 경우를 찾아야 합니다.

문제 풀이 접근 방식

1. 입력 데이터 처리 및 총합 계산:

   • 먼저 9명의 난쟁이 키를 입력받고, 이들의 키의 총합을 구합니다.

2. 제거할 두 난쟁이 찾기:

   • 두 명의 난쟁이를 제외한 7명의 키 합이 100이 되려면, 두 명의 키 합은 총합 - 100이 되어야 합니다.
   • 이 조건을 만족하는 두 명의 난쟁이를 찾고, 이들의 위치를 배열에서 마지막 두 위치로 이동시킵니다. 이로써 제거할 난쟁이들을 쉽게 처리할 수 있습니다.

3. 제거하지 않은 7명의 난쟁이 키 정렬:

   • 선택된 7명의 난쟁이 키를 오름차순으로 정렬합니다.

4. 결과 출력:

   • 정렬된 7명의 난쟁이 키를 출력합니다.

코드 설명

아래는 해당 문제를 해결하기 위한 Java 코드를 작성한 것입니다.

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

public class P2309 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] heights = new int[9];
        int sum = 0;

        // 9명의 난쟁이 키를 입력받고 합을 계산
        for(int i = 0; i < 9; i++){
            heights[i] = Integer.parseInt(br.readLine());
            sum += heights[i];
        }

        int temp = 0;

        // 합이 sum - 100이 되는 두 난쟁이를 찾아서 배열의 마지막 두 위치로 이동
        for(int i = 0; i < 8; i++){
            for(int j = i+1; j < 9; j++){
                if(heights[i]+heights[j] == sum - 100){
                    // 첫 번째 난쟁이 이동
                    temp = heights[i];
                    heights[i] = heights[7];
                    heights[7] = temp;

                    // 두 번째 난쟁이 이동
                    temp = heights[j];
                    heights[j] = heights[8];
                    heights[8] = temp;
                }
            }
        }

        // 남은 7명의 난쟁이 키를 오름차순 정렬
        for(int i = 0; i<6; i++){
            for(int j = i+1; j<7; j++){
                if(heights[i] > heights[j]){
                    temp = heights[i];
                    heights[i] = heights[j];
                    heights[j] = temp;
                }
            }
        }

        // 결과 출력
        for(int i = 0; i < 7; i++){
            System.out.println(heights[i]);
        }
    }
}

핵심 아이디어

• 탐색 범위 줄이기: 모든 경우의 수를 살펴보는 방법은 비효율적이기 때문에, 두 명의 난쟁이의 키 합이 sum - 100이 되는지를 조건으로 삼아 탐색 범위를 줄였습니다.
• 간단한 정렬 사용: 정렬 알고리즘 중에서 자주 사용하는 버블 정렬을 사용하여 7명의 키를 오름차순으로 정렬했습니다. 물론 효율성 측면에서는 더 빠른 정렬 알고리즘을 사용하는 것이 좋겠지만, 작은 데이터셋에서는 간단한 방법이 더 직관적일 수 있습니다.

결론

이 문제는 브루트포스(완전 탐색) 기법을 활용하여 해결할 수 있습니다. 가능한 모든 경우를 조사해도 문제의 제약 조건 내에서는 충분히 빠르게 답을 구할 수 있습니다. 이러한 접근 방식은 작은 데이터셋에서 유용하며, 문제의 조건을 만족하는지 여부를 정확하게 판단하는 데 도움을 줍니다.

이 게시물이 백준 2309번 문제를 푸는 데 도움이 되기를 바랍니다! 댓글이나 질문은 언제든 환영입니다. Happy Coding! 😊