[백준] 2309번 일곱 난쟁이 JAVA 완전탐색

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

문제를 읽다가 너무 귀여워서 피식했다 ㅋㅋㅋ

 

풀이 방법

9명 중 가짜 2명을 골라내야 되는데 키의 합이 100이라는 것이 힌트.

7명의 조합을 찾으려면 for문이 말도 안 되게 깊어지니까

가짜 2명을 완전탐색으로 빼고 더한 값이 100인지 체크하는 방식으로 풀었다.

 

코드

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = 9; //난쟁이는 9명
        int totalHeight = 100;
        int[] height = new int[num];
        int liar1 = 0;
        int liar2 = 0;

        for(int i=0; i<num; i++){
            height[i] = Integer.parseInt(reader.readLine());
        }

        Arrays.sort(height); //마지막 출력을 위한 선정렬

        boolean isFind = false;
        for(int i=0; i<num-1; i++){
            for(int j=i+1; j<num; j++){
                int sum = 0;
                for(int k=0; k<num; k++){
                    if(k!=i && k!=j){
                        sum+=height[k];
                    }
                }
                if(sum == totalHeight){
                    liar1 = i;
                    liar2 = j;
                    isFind = true;
                    break;
                }
            }
            if(isFind)  break;
        }
        
        for(int i=0; i<num; i++){
            while(i == liar1 || i == liar2){
                ++i;
            }
            if(i < num)   System.out.println(height[i]);
        }
        reader.close();
    }
}