풀이
문제를 풀고 나서 다른 분들의 코드를 보다가 lower_bound를 저렇게 쓸 수 있다는 사실에 감명받았다.
양수가 음수로 변하면, 양수일 때 더 큰 수가 음수에선 더 작은 수가 되는데
양수 중에서 작은 수와 음수 중에서 가장 작은 수를 고르게 되면 넓은 범위를 찾게 된다.
*lower_bound(res, res + i, now) = now;를 통해 먹이사슬인지 판단할 수 있다.
새로운 데이터가 쌓이지 못하고 덮어쓰게 되면 INF의 값이 배열의 뒤쪽에 누적되게 되고,
INF의 lower_bound가 답이 된다.
코드
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9 + 123;
const int N_ = 5e5 + 1;
int N;
pii range[N_], res[N_];
int main() {
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
int a, b;
scanf("%d%d%d", &a, &a, &b);
range[i].first = -a, range[i].second = b;
}
sort(range, range + N);
for (int i = 0; i < N; ++i) {
pii now;
now.first = range[i].second;
now.second = range[i].first;
res[i].first = res[i].second = INF;
*lower_bound(res, res + i, now) = now;
}
printf("%d", lower_bound(res, res + N, pii(INF, INF)) - res);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이