boj 19623 회의실 배정 4

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

 

회의는 한번에 하나만 진행이 가능하며, 주어지는 N개의 회의들을 적절하게 배정하여 최대 인원을 구하는 문제입니다.

저는 dp + parametric search로 접근했습니다.

dp[N]: N번째 회의부터 모을 수 있는 최대 인원

 

우선 회의들을 시작시간 기준 오름차순으로 정렬합니다.

그리고 해당 회의를 진행하거나, 진행하지 않거나 두가지를 모두 확인할 수 있습니다.

 

이번 회의를 넘긴다면 바로 idx + 1번째 회의로 넘어가면 되고,

이번 회의를 진행한다면 회의가 끝나는 시간을 기준으로 가장 빠르게 시작하는 회의로 넘어갈 수 있습니다.

다음 회의는 파라매트릭 서치를 통해 구할 수 있습니다.

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 100001
using namespace std;
 
typedef struct Node {
    int l, r, s;
}Node;
 
Node list[MAX];
int dp[MAX];
int N;
 
bool cmp(Node a, Node b) {
    return a.l < b.l;
}
 
int bs(int x) {
    int l = 0;
    int r = N;
    while (l < r) {
        int m = (l + r) >> 1;
        if (list[m].l >= x) r = m;
        else l = m + 1;
    }
    return l;
}
 
int solve(int idx) {
    if (idx >= N) return 0;
 
    int& ret = dp[idx];
    if (ret != -1) return ret;
 
    return ret = max(solve(idx + 1), list[idx].s + solve(bs(list[idx].r)));
}
 
void func() {
    sort(list, list + N, cmp);
    memset(dp, -1, sizeof(dp));
    cout << solve(0) << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].l >> list[i].r >> list[i].s;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}