Machineboy空
1931: 회의실 배정 - 그리디 본문
https://www.acmicpc.net/problem/1931
문제요약
한 개의 회의실, 겹치지 않게 최대한 많은 회의를 진행하려면?
난이도
Silver 1
풀이 포인트
- 그리디
- 가장 첫번째 회의는 진행한다고 가정하고 그 다음에 열 수 있는 회의부터 고려
REVIEW
우선 문제를 제대로 안 읽어서 해당 회의를 모두 진행할 수 있는 최소 회의실 수를 구하는 줄 알고,
범위를 봤는데 2^32-1? 포기해버렸다.
아직 pair, map, set 등 자료 구조를 적절히 자유자재로 구사할 줄 모르는 것 같다.
요런 아이큐 테스트 스러운 문제는 꼭 맞추고 싶은데 또 답으로 달려갔기에 반성.
CODE
#include <bits/stdc++.h>
using namespace std;
int from, to, n, idx = 0, ret =1;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>> n;
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
cin >> from >> to;
v.push_back({to, from});
}
sort(v.begin(), v.end());
from = v[0].second; // 1
to = v[0].first; //4
for(int i = 1; i < n; i++){
//3 < 4
// 0 < 4
if(v[i].second < to) continue;
// 5 > 4
from = v[i].second; //7
to = v[i].first; //5
ret++;
}
cout << ret << '\n';
return 0;
}
'Computer > Coding Test' 카테고리의 다른 글
14469: 소가 길을 건너간 이유 3 - 그리디 (1) | 2024.06.09 |
---|---|
11866: 요세푸스 문제 0 - queue (0) | 2024.06.07 |
1987 : 알파벳 - DFS, BFS (0) | 2024.04.02 |
14497 : 주난의 난 - bfs, dfs (0) | 2024.04.01 |
14620 : 꽃길 - dfs (0) | 2024.03.28 |