본문 바로가기

Problem Solving/문제풀이

[BOJ] 1931 회의실배정

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


 그리디 알고리즘의 대표주자 회의실배정이다.

 사실 다 아는 문제니까 그냥 넘어가도 되겠지 이러면서 이제까지 한번도 구현을 안해봤는데, 채점해보니까 처음에 틀렸다 ㅡㅡ

 풀이 방법은 가장 끝나는 시간이 빠른 회의, 만약 같다면 시작을 더 빨리 하는 회의부터 그리디하게 선택하는 것이다. 끝나는 시간이 빠른 건 끝나는 시간이 빠를수록 더 많이 회의를 진행할 수 있으니까 그렇다고 쳐도 대체 왜 시작을 더 빨리 하는 회의부터 선택하는지는 잘 몰랐었는데 틀리고 나서 생각해 보니까 (7,8), (8,8) 등의 회의가 존재하면 두개를 다 먹을 수 있더라.

 구현은 간단하게 STL sort를 이용해서 정렬했다. 아직도 sort를 사용자 정의 함수로 정렬하는 것에는 익숙하지 않다...

 난이도는 1.5/5 정도라고 생각한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
bool compare(pair<intint> a, pair<intint> b)
{
    if(a.second<b.second) return true;
    else if(a.second>b.second) return false;
    if(a.first<b.first) return true;
    else return false;
}
 
int main()
{
    int n,time=0,s=0;
    vector<pair<intint> > V;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int t1,t2;
        scanf("%d %d",&t1,&t2);
        V.push_back(make_pair(t1,t2));
    }
    sort(V.begin(),V.end(),compare);
    for(int i=0;i<V.size();i++)
    {
        if(time<=V[i].first)
        {
            time=V[i].second;
            s++;
        }
    }
    printf("%d",s);
    return 0;
}
 
cs


'Problem Solving > 문제풀이' 카테고리의 다른 글

[BOJ] 1992 쿼드 트리  (0) 2018.02.05
[BOJ] 1922 네트워크 연결  (0) 2018.02.02
[BOJ] 1005 ACM Craft  (0) 2018.02.02
[BOJ] 2439 탑  (0) 2018.02.01
[BOJ] 1011 Fly me to the Alpha Centauri  (1) 2018.02.01