BOJ 2075 - N번째 큰 수

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

2075번: N번째 큰 수

라이님블로그의 풀이를 리뷰.

 

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	priority_queue<int, vector<int>, greater<int>> pq; //최소힙
	for (int i = 0; i < n; i++) {
		for (int j = 0,a; j < n; j++) { //n개의 원소를 입력받아 힙에 저장
			cin >> a;
			pq.push(a);
		}
		if (i == 0) continue; //첫 n개의 원소를 집어넣은 상태에서 시작.
		for (int j = 0; j < n; j++) pq.pop(); //n개의 원소를 pop
	}
	cout << pq.top() << '\n';
}

 

매 입력마다 n개의 수가 들어오는데, i+1번째 입력으로 들어오는 n개의 수들의 집합 A,  i번쨰 입력으로 들어왔던 n개의 수들의 집합을 B라고 하자. 이 때 A의 수들은 적어도 하나의 B의 수보단 크다.

 

위 성질을 이용해서 n개의 새로운 원소를 최소힙에 넣고 n번 pop하면 top에 있는 원소가 n번째 큰 수가 된다.

 

 

 

어떻게 이런 생각을 하지.. 그냥 LIS처럼 외워야겠다. 금방 까먹을것 같다 ㅜㅜ