solved.ac CLASS 3 백준 1931 회의실 배정

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

 

문제 핵심 : 정렬 후 그리디

 

1. 문제를 처음에 풀 때 들어올 수 있는 최대 크기가 100,000 이었으므로 n^2 으로는 못풀어서 브루트포스는 배제했다.

2. 따라서 n log n 이나 n 으로 풀 수 있는지 확인했다.

3. input case 를 적절하게 정렬을 하면 시간을 충분히 줄일 수 있을 것 같았다. (사실 이것도 긴가민가 했음)

 

정렬의 기준 :

input case 에서 들어오는 start, end 값들을 pair vector 로 표현했다.

문제에서 start 와 end 중에서 end 가 중요하다는 것을 깨달았다. 

end 를 기준으로 오름차순 정렬을 하게 되면 앞에서부터 차례대로 순회하면서 조건을 만족하면 회의 개수를 올려주었다.

 

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

using namespace std;

int N, startInp, endInp;
vector<pair<int, int>> semTimeVec;

bool compare(pair<int, int> &a, pair<int, int> &b){
    if(a.second == b.second){ // 끝지점이 같을 때
        return a.first <= b.first; // 시작지점이 큰 순으로 정렬
    }else{
        return a.second < b.second;
    }
}

int main(void){
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> startInp >> endInp;
        semTimeVec.push_back(make_pair(startInp, endInp));
    }
    
    sort(semTimeVec.begin(), semTimeVec.end(), compare);
    
    int semEnd = semTimeVec[0].second;
    int semCnt = 1;

    for (int i = 1; i < semTimeVec.size(); i++) {
        if(semEnd > semTimeVec[i].first) { // 앞의 회의시간의 끝시간이 뒤의 회의시간의 시작시간보다 크면 뒤의 회의는 추가불가
            continue;
        }else{
            semEnd = semTimeVec[i].second;
            semCnt++;
        }
    }
    
    cout << semCnt << '\n';
    
    return 0;
}

시행착오 :

처음에 compare 함수를 작성할 때 end 기준 오름차순 정렬, end 가 같을 때 start 는 내림차순 정렬을 했다.

이는 차이가 가장 작은 것을 먼저 선택했을 때 유리할 것 같았다. 하지만 아래 반례를 만족하지 못했다.

 

2

1 1

0 1

 

시행착오의 소스는 88 프로에서 틀렸다고 나오는데 사실 질문게시판을 통해서 위의 반례를 찾아내었고 아직 정확히 왜 start 정렬을 할 때 오름차순으로 해야 하는지 정확한 이해가 부족한 것 같다. 다른 문제를 풀다가 혹시 완벽히 이해가 될 때 다시 포스트를 수정하겠다.