[C/C++] 백준 - 2075번 : N번째 큰 수

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

2075번: N번째 큰 수

문제만 읽고 보면 정말 쉬워보여서 그냥 짜고 제출했는데 메모리 초과가 떴다.

문제를 보니 메모리 제한이 12MB였고 내가 한 방식대로 모든 수들을 우선순위 큐에 넣고 해결하려하면 메모리 초과가 날 수밖에 없다. 그러면 어떻게 해결해야하냐면 문제의 힌트가 주어져있다.

NxN 형태로 수가 입력이 되고 모든 수는 자신의 한 칸 위의 수보다 크다. 즉 가장 위에 있는 수들이 그 열의 수들 중 가장 작은 값이고 가장 아래에 있는 수가 그 열의 수 중 가장 큰 값이다.

그래서 우선순위 큐에 처음에는 N개의 수만 가장 큰 수들만 값과 위치를 같이 넣어주는 것이다.

그리고 N-1개까지 우선순위 큐에서 값을 빼주고 빼준 값 위에 넣을 수 있는 수가 존재하면 추가로 넣어주는 방법이다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <map> 
#include <algorithm>
#include <cmath>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define INF 987654321
#define Mod 10007
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int board[1501][1501];

int main() {
	CUNLINK;
	int N;
	cin >> N;
	//vector<vector<int>> board(N, vector<int>(N, 0));
	priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>> pq;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < N; i++) pq.push({ board[N - 1][i], {N - 1,i} });
	int Cnt = 0;
	while (!pq.empty()) {
		if (Cnt == N - 1) break;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();
		if(y != 0) pq.push({ board[y - 1][x], {y - 1, x} });
		Cnt++;
	}
	cout << pq.top().first;
	return 0;
}