[BOJ/C++] 백준 1931번: 회의실 배정

 

🔗 문제 링크 : https://www.acmicpc.net/problem/1931

 

 

💀 2% 틀렸습니다!

 

19번째 줄 전에 `cur`과 `cnt`를 선언하는 과정에서 `cnt`만 `0`으로 초기화 했을 때 생긴 문제이다.

`cur`도 `0`으로 초기화 해줘야, 정상적인 회의 시간 비교가 가능하다.

 

 

---

 

문제

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

 

 

 

 

 

입출력 예시

입력

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

 

 

출력

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

 

 

 

입출력 예시

 

 

 

---

 

풀이 

그리디 알고리즘 문제다.

"다음 회의로 적합한 회의는 끝나는 시간이 가장 빠른 회의"임을 고려하면 해결이 가능하다.

 

`vector<pair<int, int>>`에 회의 시간 정보에 대해 입력 받을 때, 순서를 `<회의 끝나는 시간, 회의 시작 시간>`으로 입력 받아 저장한다.

순서를 바꿔서 입력 받는 이유는 탐색 전, 정렬할 때 끝나는 시간이 빠른 순으로 정렬하기 위함이다.

 

    int cnt = 0;
    int cur = 0;
    for (int i = 0; i < N; i++) {
        if (cur <= p[i].second) {
            cur = p[i].first;
            cnt++;
        }
    }

for문을 돌면서 `현재 회의의 끝나는 시간 <= 다음 회의 시작 시간` 이면, 카운트(`cnt`)를 `1` 증가시키며

다음 회의 끝나는 시간을 현재 회의 끝나는 시간으로 갱신해 준다.

 

 

전체 풀이는 아래와 같다.

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;

    vector<pair<int, int>> p(N); // <끝나는 시간, 시작 시간>
    for (int i = 0; i < N; i++) {
        cin >> p[i].second >> p[i].first;
    }
    sort(p.begin(), p.end());
    int cnt = 0;
    int cur = 0;
    for (int i = 0; i < N; i++) {
        if (cur <= p[i].second) {
            cur = p[i].first;
            cnt++;
        }
    }
    cout << cnt;
}

 

 

 

---