[BOJ] #2309 - 일곱 난쟁이

※ 문제에 대한 저작권은 BAEKJOON ONLINE JUDGE에 있습니다.

💡 출처

---

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

2309번: 일곱 난쟁이

 

💡 문제

---

[설명]

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다.

일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다.

뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

 

💡 아이디어

---

일단 9명의 키의 합을 구한다.

그리고 9명 중 2명이 잘못된 난쟁이이므로 이중 for문을 통해 총합에서 어떤 2명의 키를 뺐을 때 100이 되는 지점을 찾는다.

그럼 남은 7명이 진짜 난쟁이라고 볼 수 있다.

이 7명의 키를 정렬하여 출력하면 답을 구할 수 있다.

 

💡 소스코드

---

package BOJ;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class BOJ_P2309_일곱_난쟁이 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./BOJ_INPUT/BOJ_P2309_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int[] tall = new int[9];
		ArrayList<Integer> result = new ArrayList<>();
		int sum = 0;
		int flag = 0;

		for (int i = 0; i < 9; i++) {
			tall[i] = Integer.parseInt(br.readLine());
			sum += tall[i];
		}

		for (int i = 0; i < 9; i++) {
			for (int j = i + 1; j < 9; j++) {
				if (sum - tall[i] - tall[j] == 100) {
					for (int k = 0; k < 9; k++)
						if (k != i && k != j)
							result.add(tall[k]);
					flag = 1;
					break;
				}
			}
			if(flag == 1)
				break;
		}
		
		Collections.sort(result);
		for(int i = 0; i < result.size(); i++)
			System.out.println(result.get(i));
	}
}

 

💡 결과

---

난쟁이의 수가 9명이고 찾아야 하는 가짜 난쟁이는 2명이기 때문에 이중 for문을 이용해 풀었다.

하지만, 난쟁이의 수와 가짜 난쟁이의 수가 많아진다면 반복문으로 해결하기엔 시간이 오래 걸리기 때문에

완전 탐색으로 문제를 해결할 수 있을 것 같다.