[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)3040번, 백설 공주와 일곱 난쟁이

문제 링크

3040번: 백설 공주와 일곱 난쟁이

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 9명의 난쟁이 중 진실된 7명의 난쟁이가 존재합니다.

2. 진실된 7명의 난쟁이 키의 합은 100입니다.

3. 진실된 7명의 난쟁이의 키를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 9명의 난쟁이의 합을 구한 뒤, 잘못된 난쟁이 2명을 탐색합니다.

 

3. 거짓된 난쟁이 2명을 제외한 진실된 난쟁이 7명의 키를 결과로 출력합니다.

 

 

잘못된 난쟁이 탐색.

 

9명의 난쟁이의 키를 모두 더한 뒤

 

9명 중 2명을 선택하는 모든 경우를 탐색합니다.

 

9명 키의 합 - 2명의 키의 합 = 100

 

만족할 때

 

2명을 제외한 난쟁이가 진실된 난쟁이입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

	난쟁이1	난쟁이2	난쟁이3	난쟁이4	난쟁이5	난쟁이6	난쟁이7	난쟁이8	난쟁이9
키	7	8	10	13	15	19	20	23	25

 

2. 9명의 난쟁이의 합을 구한 뒤, 잘못된 난쟁이 2명을 탐색합니다.

9명 난쟁이 키의 합

7 + 8 + 10 + 13 + 15 + 19 + 20 + 23 + 25 = 140

 

2명을 선택하는 모든 경우 탐색

 

난쟁이 1 + 난쟁이 2 : 15 ▶ 140 - 15 = 125  : 불만족!

난쟁이 1 + 난쟁이 3 : 17 ▶ 140 - 17 = 123  : 불만족!

난쟁이 1 + 난쟁이 4 : 20 ▶ 140 - 20 = 120  : 불만족!

....

난쟁이 5 + 난쟁이 9 : 40 ▶ 140 - 40 = 100  : 만족!

 

거짓된 난쟁이 : 난쟁이 5, 난쟁이 9

 

3. 거짓된 난쟁이 2명을 제외한 진실된 난쟁이 7명의 키를 결과로 출력합니다.

 

거짓된 난쟁이를 제외한 진실된 난쟁이들

 

	난쟁이1	난쟁이2	난쟁이3	난쟁이4	난쟁이6	난쟁이7	난쟁이8
키	7	8	10	13	19	20	23

 

7 8 10 13 19 20 23을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 난쟁이의 키를 받으면서 9명 난쟁이 키의 합을 구합니다.
• 9명 중 2명을 선택하는 모든 경우를 탐색하여 거짓된 난쟁이 2명을 탐색합니다.
• 거짓된 난쟁이를 제외한 난쟁이의 키를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] arr = new int[9];
        int sum = 0;
        //9명의 난쟁이 정보 저장 및 키의 합 구하기
        for(int i=0;i<9;i++){
            arr[i] = Integer.parseInt(br.readLine());
            sum += arr[i];
        }
        int first = -1, second = -1;
        boolean check = false;	//거짓된 난쟁이 찾았는지 확인하는 변수
        //9명 중 2명을 선택하는 모든 경우 탐색
        for(int i=0;i<9;i++){
            for(int j=i+1;j<9;j++){
                //거짓된 2명의 난쟁이 찾았을 때
                if(sum - (arr[i] + arr[j]) == 100){
                    check = true;
                    //난쟁이 번호 저장
                    first = i;
                    second = j;
                    break;
                }
            }
            if(check)	//거짓된 난쟁이 발견되었을 때 탐색 종료
                break;
        }
        //거짓된 난쟁이를 제외한 키의 정보 BufferedWriter 저장
        for(int i=0;i<9;i++){
            if(i == first || i == second)
                continue;
            bw.write(arr[i] + "\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}