백준 1931 회의실 배정 C++

- 문제

문제 보러가기

그리디 알고리즘을 통해 간단하게 해결할 수 있는 문제입니다. 문제를 처음 봤을 때 최근에 풀었던 배낭 문제(Knapsack problem)라고 생각을 하고 노트를 펼쳤는데, 숫자를 적다보니 그냥 단순하게 다음으로 가능한 회의들 중 끝나는 시간만 빠르면 가장 많은 회의를 가질 수 있다는 것을 알 수 있었습니다.

- 문제 풀이

• vector<pair<int, int>> 구조를 사용하여 입력 끝나는 시간을 pair의 첫 번째 인자로 시작 시간을 두 번째 인자로 시작하는 시간을 넣어준다.
• sort 함수를 통해 정렬해준다.
• 반복문을 통해 벡터 원소의 두 번째 인자(시작시간) 이 마지막 회의 종료 시간보다 시작 시간 보다 작다면 마지막 회의 시간을 벡터 원소의 첫 번째 인자(끝나는 시간)을 넣어준 후 result에 1을 더해준다.

- 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N, start, end;
    vector<pair<int, int>> times;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> start >> end;
        times.push_back(pair<int, int>(end, start));
    }

    sort(times.begin(), times.end());

    int lastTime = 0;
    int result = 0;

    for(auto t : times){
        if(t.second >= lastTime) {
            lastTime = t.first;
            result ++;
        }
    }

    cout << result;
    return 0;
}

처음에 algorithm 라이브러리의 sort 함수에 끝나는 시간을 기준으로 정렬하기위한 compare함수를 정의하여 사용했는데 틀렸습니다.. 정확한 이유를 찾지는 않았지만 pair의 두 번째 인자로 끝나는 시간을 넣었었는데, 두 번째 인자만을 기준으로 정렬하고 첫 번째 인자값은 전혀 정렬이 되지 않아서 틀린거라고 생각이 듭니다. 따라서 먼저 비교하고 싶은 끝나는 시간을 첫 번째 인자로 하고 sort 함수의 비교함수를 default로 주었습니다. 이렇게하면 pair의 첫 번째 인자로 오름차순 정렬 후 두 번째 인자로 오름차순 정렬을 할 수 있습니다.