[백준] 2309번 : 일곱 난쟁이 (C++)

2309번: 일곱 난쟁이

 

📚 문제 한 줄 요약

난쟁이의 키의 합이 100인 것을 이용해 아홉 명 중 누가 진짜 일곱 명의 난쟁이인지 알아내기

 

📚 문제 포인트 : 9명 중 7명의 키의 합이 100, 키를 오름차순으로 출력

 

📚 풀이 (핵심 : 아홉 명 중 일곱 명 골라내는 방법 생각하기)

여기서 포인트는 아홉 명 중 합이 100이 되는 일곱 명을 알아내는 것인데

이를 달리 말하면 입력받은 데이터 중 두 개의 값을 빼서 합이 100이 되는 값을 찾아라는 말과 같다.

위를 이용해서 for문으로 전체 탐색했다.

 

주의할 것은 출력 값이 오름차순으로 정렬된 값이기 때문에

미리 난쟁이를 찾기 전에 정렬을 해줘야 풀이가 깔끔해진다.

 

문제 해결 순서는 다음과 같이 계획했다.

1. 입력 데이터 받기 (난쟁이의 키 9개)
2. 난쟁이의 키 정렬하기
3. 일곱 난쟁이 가려내기 = 값을 뺐을 때 합이 100이 되게 만드는 2명 찾기
4. 위에서 찾은 2명 빼고 출력하기

 

위에서 계획한 대로 작성한 코드는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	
	// 1. INPUT DATA
	int dwarf[9];
	int sum = 0;
	for (int i = 0; i < 9; i++) {
		cin >> dwarf[i];
		sum += dwarf[i];
	}

	// 2. SORT
	sort(dwarf, dwarf+9);

	// 3. SEARCH
	int noDwarf1 = -1, noDwarf2 = -1;
	for (int i = 0; i < 8; i++) {
		for (int j = i+1; j < 9; j++) {
			if (sum-dwarf[i]-dwarf[j] == 100) {
				noDwarf1 = i;
				noDwarf2 = j;
				break;
			}			
		}
	}
	
	// 4. OUTPUT DATA
	for (int i = 0; i < 9; i++) {
		if (i != noDwarf1 && i != noDwarf2)
			cout << dwarf[i] << '\n';		
	}
}