백준-2309번/일곱 난쟁이 (java)

 

 

이 문제는 브루트포스 알고리즘에 대해서 숙지하고 풀어야 하는 문제이다.

 

브루트포스 알고리즘이란?

- 무차별 대입법이라고도 하며 조합 가능한 모든 경우를 하나씩 대입해 보는 알고리즘이다.(노가다)

특징으로는 모든 경우를 탐색하므로 정확도 100%를 보장하지만 비효율적이다.

 

 

-문제 풀이

 

일곱난쟁이 입력 = 9명 

9명에서 7명을 뽑았을때 키의 합 = 100

브루트 포스 알고리즘으로 7명의 키 합이 100인 경우를 추출

        for(int i=0; i<8; i++){
            for(int j=i+1; j<9; j++){
                if(sum-arr[i]-arr[j]==100){
                    arr[i]=0;
                    arr[j]=0;
                    Arrays.sort(arr);
                    for(int k=2; k<9; k++){
                        System.out.println(arr[k]);
                    }
                    return;
                }
            }
         }

i번째 와 j번째 난쟁이의 키를 전체 합에서 뺐을때 100이면 i와 j번째 난쟁이의 키를 0으로 만들어주고 정렬 후 i와 j를 건너뛴 2부터 배열을 출력해준다.

 

(j가 i+1부터인 이유 : 이 전에 검색하고 넘어간 경우이기 때문)

 

 

 

 

 

 

 

<정답 코드>

import java.util.Arrays;
import java.util.Scanner;

public class Problem2309 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[9];
        int sum=0;
        for(int i=0; i<9; i++) {
            arr[i]=scanner.nextInt();
            sum+=arr[i];
        }

        for(int i=0; i<8; i++){
            for(int j=i+1; j<9; j++){
                if(sum-arr[i]-arr[j]==100){
                    arr[i]=0;
                    arr[j]=0;
                    Arrays.sort(arr);
                    for(int k=2; k<9; k++){
                        System.out.println(arr[k]);
                    }
                    return;
                }
            }
        }



    }
}