[백준] 1931번: 회의실 배정 C++로 풀어보기

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

1931번: 회의실 배정

 

1931번 설명

생각

그리디 알고리즘을 이용해서 풀어야되는 문제이다.

 

 

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. (출처: 나무위키)

 

 

현재 선택한 회의가 있다고 가정하자.

그러면 다음에 있는 회의 중에서 가장 종료 시간이 빠른 회의를 선택해야 최대한 많은 회의를 진행할 수 있다.

 

 

1. 회의를 종료 시간이 가장 빠른 순서로 정렬한다.

(만약 종료 시간이 같다면 시작 시간이 더 빠른 회의가 앞으로 온다)

 

2. 종료 시간을 저장할 변수를 만들고, 그 변수에 0을 집어넣는다. (이하 endtime)

 

3. 루프를 진행하면서 만약 시작 시간이 현재 택한 회의의 종료 시간보다 느리거나 같다면

(어차피 종료 시간 순으로 정렬을 했으니, 이 조건만 통과하면 최적해가 된다.)

 

4. endtime을 갱신하고, 회의 개수를 나타내는 변수에 1을 더해준다.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt = 0; // 회의 개수

struct meet { // 시작 시간과 종료시간을 입력받는 구조체
    ll st;
    ll en;
};

ll cmp(meet a, meet b) { // 종료 시간이 빠른 순서대로 정렬
    if (a.en != b.en) {
        return a.en < b.en;
    }
    else { // 종료 시간이 같다면 시작 시간이 빠른 순서대로 정렬
        return a.st < b.st;
    }
    
}


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;

    struct meet* mt = new struct meet[n]; // 구조체 동적할당

    for (ll i = 0; i < n; i++) { // 시작 시간과 종료 시간 입력
        cin >> mt[i].st;
        cin >> mt[i].en;
    }

    sort(mt, mt + n, cmp); // 종료 시간이 빠른 순서대로 정렬


    int endtime = 0;
    for (ll i = 0; i < n; i++) {
        if (endtime <= mt[i].st) { // 시작 시간이 현재 회의의 종료 시간보다 느리거나 같다면
            endtime = mt[i].en; // 종료 시간 갱신
            cnt++; // 회의 개수 추가
        }
    }
    

    cout << cnt; // 출력

    delete[] mt; // 동적할당 해제


}

 

결과

1931번 결과