[C++][백준] - 백설공주와 일곱 난쟁이 (3040번)

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

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

🔔 문제 : 

9명의 난쟁이가 있습니다.

 

각각 다른 키를 1 <= 키 <= 99 만큼의 자연수로 되어있습니다.

 

이 중 진짜 난쟁이는 7명입니다.

 

진짜 난쟁이들의 키의 합은 100입니다. 이는 경우의 수가 1개만 존재합니다.

 

난쟁이들의 키를 입력받아 진짜 난쟁이들의 키를 출력하는 문제입니다.

---

🔔 Kick Point :

 

2중 반복문을 통하여 구한다면 시간 복잡도로 O(N^2) 만큼의 성능이 나옵니다.

 

저는 입력값을 정렬을 한 후O(nlgn), 양쪽 슬라이딩O(n) 을 통하여 합쳐서 O(nlgn) 시간복잡도로 줄이는 방법을 선택하였습니다.

 

풀이 방법으로는 난쟁이들의 키를 합친후, 100을 빼면 가짜 난쟁이 2명의 키의 합을 알 수 있습니다.

이를 정렬된 값의 슬라이딩을 통해 쉽게 구해 냅니다.

---

🔔 Code :

#include <iostream>
#include <algorithm>
using namespace std;

// sorting된 난쟁이들 O(N) + sort O(nlgn) = O(nlgn)
int main() {
	int sum(0); int dwarf[9];

	for (int i = 0; i < 9; i++) {
		cin >> dwarf[i];
		sum += dwarf[i];
	}
	sum -= 100;

	sort(dwarf, dwarf+9);

	int lPivot = 0; int rPivot = 8;
	while (rPivot > lPivot) {
		int tmp = dwarf[lPivot] + dwarf[rPivot];
		
		if (tmp == sum) break;
		else if (tmp > sum) rPivot--;
		else lPivot++;
	}

	for (int i = 0; i < 9; i++) {
		if (i == lPivot || i == rPivot) continue;
		cout << dwarf[i] << '\n';
	}
	
}

---