N번째 큰 수
시간 제한1초메모리 제한12 MB
각 열이 위에서 아래로 증가하는 N x N 행렬에서 전체 원소 중 N번째로 큰 값을 효율적으로 구하는 문제입니다.
문제
크기가 N × N인 표에 서로 다른 정수 N^2개가 들어 있다. 각 수는 바로 위 칸에 있는 수보다 크다. 즉, 같은 열에서는 아래로 내려갈수록 수가 커진다.
아래는 N = 5인 표의 한 모습이다.
이와 같은 표가 주어질 때, 전체 N^2개의 수 중에서 N번째로 큰 수를 구하라.
입력
첫째 줄에 N (1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 정수가 주어진다. 표에 적힌 수는 모두 -10^9 이상 10^9 이하의 정수이다.
출력
첫째 줄에 N번째로 큰 수를 출력한다.