코드 복사/붙여넣기 하는 당신이 아름답습니다.

2532 : 먹이사슬

풀이

문제를 풀고 나서 다른 분들의 코드를 보다가 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-21 00:35

Read more posts by this author