[BOJ-1931][C++] 회의실 배정

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	156222	49243	34665	29.706%

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 $2^{31}-1$보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

예제 출력 1

4

 

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

 

문제 출처

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

1931번: 회의실 배정

 

---

 

문제 해결 방법

• 실버I의 난이도이지만 정답률이 29%대인 문제이다.
• 시간 초과 문제 때문에 정답률이 낮아진 것으로 추정된다.
• 그리디 알고리즘을 이용하여 문제를 해결할 수 있었으며, 문제 해결의 핵심은 다음과 같다.
  • 입력 받은 시작 시간(@from@)과 끝나는 시간(@to@)을 2차원 벡터(@times@)에 넣는다.
    • 끝나는 시간(@to@)을 기준으로 오름차순 정렬을 해줄 것이기 때문에 더 간편하게 정렬을 해주기 위해서 2차원 벡터에는 [끝나는 시간, 시작 시간] 순서대로 값을 넣어준다.
  • 끝나는 시간(@to@)을 기준으로 오름차순 정렬을 해준다. (@sort(times.begin(), times.end();@)
  • 첫 번째 회의의 끝나는 시간을 기준값으로 정한 후 (@next = times[0].first@), 두 번째 회의부터 N번째 회의까지의 시작 시간(@times[i].second@)의 값과 비교해나간다.
    • 시작 시간의 값이 기준값보다 크거나 같을 경우(@if (next <= times[i].second)@) 카운팅을 해준다. (@cnt++@)
      • 카운팅 값을 저장하는 변수(@cnt@)의 초깃값은 1로 설정해준다.
        • 기준값을 설정할 때 첫 번째 회의의 경우를 미리 세었고, 두 번째 회의부터 비교를 해나가기 때문이다.
      • 동시에 기준값을 회의의 끝나는 시간으로 업데이트해준다. (@next = times[i].first@)

int Solution(vector<pair<int, int>> v) {
    int next;
    sort(v.begin(), v.end());    // 끝나는 시간 기준 오름차순 정렬

    next = v[0].first;
    cnt = 1;
    for (auto i = 1; i < N; i++) {
        if (next <= v[i].second) {
            cnt++;
            next = v[i].first;
        }
    }

    return cnt;
}

 

예제를 통해 알고리즘 이해하기

• @예제 입력 1@의 값들을 '끝나는 시간' 기준으로 오름차순 정렬을 해주면 다음과 같다.

회의 순서	끝나는 시간	시작 시간
1	4	1
2	5	3
3	6	0
4	7	5
5	8	3
6	9	5
7	10	6
8	11	8
9	12	8
10	13	2
11	14	12

• 기준값(@next@)을 첫 번째 회의의 끝나는 시간(@4@)으로 잡는다. ([1, 4]) (cnt = 1)
• 그 다음에 가능한 회의는 시작 시간이 기준값(@4@)보다 크거나 같아야 한다. 따라서 네 번째 회의(시작 시간 : @5@)를 선택할 수 있다.([1, 4], [5, 7]) (cnt = 2)
  • 기준값을 네 번째 회의의 끝나는 시간(@7@)으로 업데이트해준다.
• 그 다음에 가능한 회의는 시작 시간이 기준값(@7@)보다 크거나 같아야 하므로, 여덟 번째 회의(시작 시간 : @8@)를 선택할 수 있다.([1, 4], [5, 7], [8, 11]) (cnt = 3)
  • 기준값을 여덟 번째 회의의 끝나는 시간(@11@)으로 업데이트해준다.
• 그 다음에 가능한 회의는 시작 시간이 기준값(@11@)보다 크거나 같아야 하므로, 열 한 번째 회의(시작 시간 : @12@)를 선택할 수 있다.([1, 4], [5, 7], [8, 11], [12, 14]) (cnt = 4)
  • 기준값을 열 한 번째 회의의 끝나는 시간(@12@)으로 업데이트해준다.
• 더 이상 비교할 것이 없으므로 과정을 종료한다. [1, 4], [5, 7], [8, 11], [12, 14] 구간을 선택할 수 있으며, 최종적으로 @cnt@ 값(@4@)이 정답이 된다.

 

처음에 접근했던 방식

• 처음에 다음과 같이 2중 for 문을 이용하여 전 회의 구간을 비교하면서 카운팅 횟수의 최댓값을 구하는 방식으로 문제를 해결하려고 하였으나, 시간 초과 때문에 문제를 해결할 수 없었다.

int Solution(vector<pair<int, int>> v) {
    int next;
    sort(v.begin(), v.end());    // 끝나는 시간 기준 오름차순 정렬

    for (auto i = 0; i < N; i++) {
        next = v[i].first;
        cnt = 1;
        for (auto j = i + 1; j < N; j++) {
            if (next <= v[i].second) {
                cnt++;
                next = v[i].first;
            }
        }
        maxCnt = max(maxCnt, cnt);
    }
    
    return maxCnt;
}

• 결국 for 문을 1개만 써서 문제를 해결할 수 있다는 것을 알게 되었고, 문제를 해결할 수 있었다.
  • 끝나는 시간을 기준으로 오름차순 정렬을 했기 때문에 굳이 2중 for 문을 쓰지 않아도 됐다.
  • 왜냐하면, 상위 회의 구간의 카운팅 횟수는 하위 회의 구간의 카운팅 횟수를 포함하므로 굳이 전체의 구간을 서로 비교할 필요가 없기 때문이다.

int Solution(vector<pair<int, int>> v) {
    int next;
    sort(v.begin(), v.end());    // 끝나는 시간 기준 오름차순 정렬

    next = v[0].first;
    cnt = 1;
    for (auto i = 1; i < N; i++) {
        if (next <= v[i].second) {
            cnt++;
            next = v[i].first;
        }
    }

    return cnt;
}

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, from, to, cnt;
vector<pair<int, int>> times;

void Input() {
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> from >> to;
        times.push_back({ to, from });    // [끝나는 시간, 시작 시간]
    }
}

int Solution(vector<pair<int, int>> v) {
    int next;
    sort(v.begin(), v.end());    // 끝나는 시간 기준 오름차순 정렬

    next = v[0].first;
    cnt = 1;
    for (auto i = 1; i < N; i++) {
        if (next <= v[i].second) {
            cnt++;
            next = v[i].first;
        }
    }

    return cnt;
}

void Output() {
    cout << Solution(times) << '\n';
}

void Solve() {
    Input();
    Output();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [그리디 알고리즘]
• 실버I