취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10651번 문제인 Cow Jog이다.
문제는 아래 링크를 확인하자.

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

L을 소가 달리기 시작하는 위치, R을 소가 달리기를 마치는 위치를 의미하는 알파벳으로 사용하겠다.

시간 T동안 소 A가 L1에서 R1까지, 소 B가 L2에서 R2까지 뛰었다고 해보자. (단, L1<L2)

그렇다면, R1<R2이면 두 소는 충돌하지 않고 뛸 것이고, 그렇지 않다면 충돌할 것이라는 것을 알 수 있다.

한편, 문제에서 구하는 lane 수는 어떤 두마리 소를 골라도 달리는 중에 충돌하게 되는 집합의 최대 크기를 구하는 문제로 생각할 수 있다. 이는, (서로 다른) L이 정렬되어 입력이 들어올 때 R값들의 순서를 역순으로 살펴서 찾을 수 있는 LIS의 길이와 같다는 것을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<pair<ll, int>> arr;

bool xcomp(pair<ll, int> p1, pair<ll, int> p2) {
	if (p1.first != p2.first) return p1.first < p2.first;
	return p1.second > p2.second;
}

bool icomp(pair<ll, int> p1, pair<ll, int> p2) {
	return p1.second < p2.second;
}

int seg[262145];

int update(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = qVal;
	return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int rangemax(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; ll T; cin >> N >> T;
	
	for (int i = 0; i < N; i++) {
		ll x, v; cin >> x >> v;
		arr.push_back({ x + v * T,i });
	}

	sort(arr.begin(), arr.end(), xcomp);
	
	for (int i = 0; i < N; i++) {
		arr[i].first = i + 1;
	}

	sort(arr.begin(), arr.end(), icomp);

	int cnt = 0;
	for (auto iter = arr.rbegin(); iter != arr.rend(); iter++) {
		int temp = rangemax(1, N, 1, (*iter).first, 1) + 1;
		if (temp > cnt) cnt = temp;
		update(1, N, (*iter).first, temp, 1);
	}

	cout << cnt;
}