BOJ 8984 막대기

사용한 알고리즘

DP, 이분탐색

알고리즘 설명

막대기을 line 배열의 저장하고, 위쪽과 아래쪽 좌표를 구분지어 저장한다.
막대기와 위쪽 아래쪽 좌표를 오름차순 정렬한다.
정렬된 막대기를 앞에서 부터 접근한다. 위 아래 좌표가 저장된 곳에서 현재 막대기와 같거나 큰 위치의 인덱스를 찾아온다.
DP를 적용하기 위해서 [막대기 위치][위/아래]의 형태로 상태를 정의한다.
위 상태를 이용하여 그전 막대기에서 가장 긴 막대기 + 현재 막대기 길이 정보를 이용하여 dp를 채워나간다.
이 막대기 길이중 가장 긴 길이를 출력한다.

풀이

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=100001;
typedef pair<int, int> P;
typedef long long ll;

int N, L, t, d, uline[MAX_N], dline[MAX_N];
P line[MAX_N];
ll dp[MAX_N][2], ret;

int main() {
	scanf("%d%d", &N, &L);
	for (int i=0; i<N; i++) {
		scanf("%d%d", &t, &d);
		line[i].first = uline[i] = t;
		line[i].second = dline[i] = d;
	}
	sort(line, line+N);
	sort(uline, uline+N);
	sort(dline, dline+N);
	for (int i=0; i<N; i++) {
		int uidx = lower_bound(uline, uline+N, line[i].first) - uline;
		int didx = lower_bound(dline, dline+N, line[i].second) - dline;
		int len = abs(line[i].first-line[i].second) + L;
		ll pt = dp[uidx][0], pd = dp[didx][1];
		dp[uidx][0] = max(pt, pd + len);
		dp[didx][1] = max(pd, pt + len);
		ret = max(ret, max(dp[uidx][0], dp[didx][1]));
	}
	printf("%lld\n", ret);
	return 0;
}