[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