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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-27 15:06

Read more posts by this author