8098 : Lecture Halls Reservation
풀이
회의실 배정이랑 비슷하게 생겼다.
오… 이거 데이터 생겨먹은 게 끝나는 시간을 기준으로 정렬해주고 싶게 생겼다.
시간의 최대 범위가 3만이므로, 각각의 시간에 대해, 해당 시간까지의 최대 해를 계산해줄 수 있다.
약간 다이나믹스러운 느낌으로
d[time] = max(d[time], d[start]+end-start)
주어진 구간의 양 끝점만 보고 삭 긁어주면 된다.
시간 범위가 3만보다 (엄청) 크다면 세그트리 등등을 이용해서 풀어줄 수 있겠다.
코드
#include <cstdio>
#include <algorithm>
using namespace std;
int n, r, d[30003];
pair<int, int> a[10002];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &a[i].second, &a[i].first);
}
sort(a, a+n);
int i = 0, t = 1;
while (t <= 30000) {
int x = a[i].second, y = a[i].first;
d[t] = max(d[t], d[t-1]);
if (y > t || i == n) {
t++;
continue;
}
d[t] = max(d[t], d[x]+y-x);
if (i < n) i++;
}
printf("%d", d[t-1]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이