[BOJ] 회의실 배경 3 19622번 C++

문제

서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N개의 회의를 회의실에 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구하자.

입력

첫째 줄에 회의의 수 N이 주어진다. 둘째 줄부터 N + 1 줄까지 공백을 사이에 두고 회의의 시작시간, 끝나는 시간, 회의 인원이 주어진다.

출력

첫째 줄에 회의실에서 회의를 진행할 수 있는 최대 인원을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.
• 모든 회의의 시작 시간과 끝나는 시간은 231 − 1보다 작거나 같은 자연수 또는 0이다.
• 모든 회의의 시작 시간과 끝나는 시간은 서로 다르다.
• 회의 인원은 1,000보다 작거나 같은 자연수 이다.

 

접근 방식

 

vector를 이용해서 세가지 이상의 값을 저장해야 할 때 tuple 을 사용할 수도 있지만

struct 구조체를 사용하면 더 간단하다

 

회의를 종료 시간을 기준으로 정렬 후, 현재 회의와 겹치지 않는 회의를 찾아서 인원수를 dp 배열에 갱신하면 된다!

단, 정렬을 하지 않거나 현재 회의와 겹치지 않는 회의를 찾고 break문을 걸지 않다면 최악의 경우 N제곱의 시간복잡도를 가져 시간 초과가 발생할 수 있음을 유의하자!

 

코드

#include <bits/stdc++.h>
using namespace std;

struct Meeting {
    int start, end, people;
};

bool compare(Meeting a, Meeting b) {
    return a.end < b.end; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;

    vector<Meeting> meetings(N);
    for (int i = 0; i < N; i++) {
        cin >> meetings[i].start >> meetings[i].end >> meetings[i].people;
    }

    sort(meetings.begin(), meetings.end(), compare);

    vector<long long> dp(N + 1, 0); 

    for (int i = 1; i <= N; i++) {
        // 현재 회의를 포함하지 않는 경우 (이전 최대값 유지)
        dp[i] = dp[i - 1];

        // 현재 회의를 포함하는 경우 (이전 회의 중 겹치지 않는 회의를 찾아 추가)
        int lastCompatible = 0; // 겹치지 않는 마지막 회의의 dp 값
        for (int j = i - 1; j > 0; j--) {
            if (meetings[j - 1].end <= meetings[i - 1].start) {
                lastCompatible = dp[j];
                break;
            }
        }

        dp[i] = max(dp[i], lastCompatible + static_cast<long long>(meetings[i - 1].people));

    }

    cout << dp[N] << '\n';
}