[BAE/<JOON> 문제풀이] 19623. 회의실 배정 4

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

19623번: 회의실 배정 4

서론

라인 스윕 DP

---

풀이

회의 구간이 겹치지 않으면서 가장 많은 인원을 회의에 참석시켜야 하므로 

겹치기 여부 판정은 라인 스윕으로, 인원수 최대화는 DP로 나눠 생각할 수 있다.

첫번째, DP 점화식은 아래와 같다.

• DP[i] = i번째 회의까지 참여시킬 수 있는 최대 인원 수
• DP[i] = max(i번째 이전의 i번째 회의와 겹치지 않고 함께 진행할 수 있는 회의 인원수 총합 + i번째 회의 인원수, i-1번째 회의까지의 최적값)

쓰다보니 말이 길어지는데 단순하게 최소 k칸 이상 떨어진 배열 요소들의 합의 최대를 구하는 문제로 바꿔 생각하면 이해가 쉽다. 

 

두번째, 겹치는지 여부에 대한 판정은 아래와 같다.

회의를 빨리 끝나는 순으로 정렬했을 때, 현재 회의 i와 겹치지 않는 이전 회의의 종료 시간은 만드시 현재 회의 i의 시작 시간보다 빠르다. 모든 회의는 종료 시간을 기준으로 정렬되어있으므로 lower_bound 를 이용해 n log n 시간에 이 항목을 구할 수 있다.

 살짝 헷갈렸던게 이 방식을 사용하면 조건을 만족하는 항목 중 가장 인덱스가 큰 요소를 구하게 될 텐데, 그 이전 인덱스가 최적인 입력은 처리하지 못하는게 아닌가 하는 부분이었다.

DP를 구상하지 않고 겹침 판정부터 작성해서 그랬는데,  DP배열은 i번째 구간까지의 최적값이 담긴 배열로 연산하기 때문에 그런 경우 i-1 번째 배열을 선택해 오류가 발생하지 않는다.

---

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
struct line {
    int s, e, i;
};
bool cmp(line a, line b) {    
    return a.e < b.e;
}
struct cmpc {
    bool operator()(line a, line b) {
        return a.i < b.i;
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n; vector<line> arr(n + 1); vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].s >> arr[i].e >> arr[i].i;
    }
    sort(arr.begin() + 1, arr.end(), cmp);
    priority_queue<line, vector<line>, cmpc> pq;
    dp[1] = arr[1].i;
    int mx = 0;
    for (int i = 2; i <= n; i++) {
        int k = lower_bound(arr.begin() + 1, arr.begin() + i + 1, arr[i].s, [](line a, int s) {return a.e <= s; }) - arr.begin() - 1;
        int s = dp[k] + arr[i].i;
        dp[i] = s > dp[i - 1] ? s : dp[i - 1];
    }    
    cout << dp[n];
    return 0;
}