728x90
반응형
1. 문제
https://www.acmicpc.net/problem/1931
2. 풀이
끝나는 시간이 빠른 회의를 우선적으로 선택함으로써 남은 시간을 최대한 활용할 수 있게 됩니다.
다시 말해, 어떤 회의가 빠르게 끝나면 그 후에 다른 회의들을 더 많이 배정할 수 있습니다.
예시)
회의 리스트:
A: 1-4
B: 3-5
C: 0-6
D: 5-7
E: 3-8
F: 5-9
G: 6-10
H: 8-11
I: 8-12
J: 2-13
K: 12-14
1. 끝나는 시간을 기준으로 오름차순 정렬을 합니다:
A: 1-4
B: 3-5
D: 5-7
F: 5-9
G: 6-10
C: 0-6
E: 3-8
H: 8-11
I: 8-12
K: 12-14
J: 2-13
2. 이제 리스트의 맨 앞에서부터 회의를 확인하며 배정합니다:
- 첫 번째 회의 A: 1-4 를 선택합니다.
- 다음 회의 B: 3-5 는 A와 겹치므로 건너뜁니다.
- 그 다음 회의 D: 5-7 는 A와 겹치지 않으므로 선택합니다.
- 회의 F, G는 D와 겹치므로 건너뜁니다.
- 회의 C는 A와 겹치므로 건너뜁니다.
- 회의 E도 A와 겹치므로 건너뜁니다.
- 회의 H: 8-11은 D와 겹치지 않으므로 선택합니다.
- I는 H와 겹치므로 건너뜁니다.
- K: 12-14는 H와 겹치지 않으므로 선택합니다.
- J는 A와 겹치므로 건너뜁니다.
결국 선택된 회의는 A, D, H, K 총 4개입니다.
이렇게 "끝나는 시간"을 기준으로 오름차순 정렬하여 탐색하는 방식으로 최대 개수의 회의를 선택할 수 있습니다.
3. 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Meeting {
int start, end;
};
bool compare(const Meeting &a, const Meeting &b) {
if (a.end == b.end) return a.start < b.start;
return a.end < b.end;
}
// 1931
/*
끝나는 시간이 빠른 회의를 우선적으로 선택함으로써 남은 시간을 최대한 활용하는 것이 문제의 핵심
*/
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int N, answer = 0, end_time = 0;
cin >> N;
vector<Meeting> meetings(N);
for (int i = 0; i < N; i++)
cin >> meetings[i].start >> meetings[i].end;
// 1. 끝나는 시간 기준으로 정렬
sort(meetings.begin(), meetings.end(), compare);
// 2. 회의를 탐색하면서 조건에 맞는 회의 선택
for (int i = 0; i < N; i++) {
if (meetings[i].start >= end_time) {
end_time = meetings[i].end;
answer++;
}
}
cout << answer;
return 0;
}
728x90
반응형
'💡 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준 - 1629] 곱셈 [C++] (0) | 2023.10.19 |
---|---|
[백준 - 11286] 절댓값 힙 [C++] (0) | 2023.10.18 |
[백준 - 1541] 잃어버린 괄호 [C++] (0) | 2023.10.16 |
[백준 - 15829] Hashing [C++] (0) | 2023.10.14 |
[백준 - 13335] 트럭 [C++] (0) | 2023.10.14 |