[백준] 1931번: 회의실 배정 풀이 및 해설(C++)

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

1931번: 회의실 배정

 

C++로 작성한 백준 문제 1931번 회의실 배정에 대한 문제 풀이다.

실버 1 문제고, 그리디 알고리즘과 정렬이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

문제

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

입력

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

출력

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

 

---

문제 파악하기

1. 회의마다 시작과 끝 시간이 다 달라 계산하기 힘들다.
2. 그러니 정렬을 사용해서 우선 시작과 끝시간에 맞게 오름차순으로 정렬해 준다.
3. 회의 시간이 적은 게 무조건 좋은 것 같지만 사실 순서대로 생각했을 때 다음 시행은 이전 탐욕시행과는 독립적이다.
4. 따라서, 그냥 회의 종료시간이 빠른 순서대로 정렬해서 계산하면 된다.

 

 

---

 

코드 및 설명

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    long long n,s,f,max=0,ans=0;
    cin>>n;
    vector<pair<long long,long long>> v;
    for(int i=0; i<n; i++){
        cin>>s>>f;
        v.push_back(pair<int,int>(f,s));
    }
    sort(v.begin(),v.end());
    for(int i=0; i<n; i++){
        if(v[i].second>=max){
            ans++;
            max=v[i].first;
        }
    }
    cout<<ans;

    return 0;
    

}

 

회의시간의 시작시간과 끝 시간은 하나의 객체처럼 움직일 것이니 pair화 해서 저장해 준다.

그리고 이를 정렬한다. 종료시간이 빠른 순서대로,  만약 종료 시간이 같다면 시작 시간이 빠른 순서대로 정리된다.

일단 일찍 끝나야 뭘 할 수 있기 때문에, 종료시간이 빠른 것부터 택하고, 다음걸로 넘어간다.

 

 

 

---

 

헤매었던 부분

문제의 가닥을 잡지 못해 많은 시간이 걸렸다. 아니 시작시간이랑 종료시간이랑 다 다른데 어떻게 하지? 걸리는 시간이 가장 적은 순서대로 채워 넣어도 안되는데? 하면서 말이다. 그래서 이번 문제는 구글신의 도움을 받아 해결했다.

[백준] 1931번 : 회의실배정 - JAVA [자바]

 

여기 티스토리 블로그 작성자 님이 그래프로 표시해 준 게 많은 도움이 되었다.

 

 

 

---

 

마무리

어떻게 해야 되지 싶은 문제가 나올 때는 정렬을 해서 일단 문제를 정갈하게 만들어보자. 방청소를 해야 집중이 잘 되듯 일단 정리하고 간단화해야 잘 되는 것 같다. 잘 안될 땐 그려보자, 그것도 도움이 된다. 그리고 정렬의 관점도 시작시간인지 종료시간인지 바꿔보아야 문제의 실마리가 잡힌다. 그리디 알고리즘을 풀 때는 이전과 어떻게 해야 독립시행이고 어떻게 해야 독립시행이 아닌지가 상당히 중요한 것 같다.