[백준][스위핑] 1931 회의실 배정 c++구현

목차

1. 문제
2. 문제 접근 방향
3. 코드 구현

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

문제

 

문제 접근 방향

생각보다 아이디어가 잘 떠오르지 않았다. 하지만 N이 100000이라는 것을 보아 O(N) 시간으로 탐색해야 한다는 것을

유추할 수 있다. 또한 경우를 줄이기 위해 정렬을 해야 한다는 것 또한 유추할 수 있다.

 

다음과 같이 3가지 정렬 기준이 나올 수 있다.

 

1. 시작점 기준으로 정렬하기

바로 반례가 나온다. 경우에서 제외시켜 준다.

 

2. 사이 크기로 정렬하기

이것 또한 반례가 바로 나온다.

 

3. 끝점 기준으로 정렬하기

이것은 반례가 안보인다. 한번 시도해볼 가치가 충분하다.

 

 

코드 구현

cpp

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>


using namespace std;

typedef long long ll;

vector<pair<ll, ll>>v;
ll N, a, b;
ll total = 0;
ll start = 0;
ll target = 0;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        v.push_back({ b, a });
    }
    sort(v.begin(), v.end());
    for (auto p : v) {
        if (total == 0) {
            total++;
            start = p.second;
            target = p.first;
            continue;
        }
        if (p.second < target) {
            ;
        }
        else {
            target = p.first;
            total++;
        }
    }
    cout << total;
    return 0;
}

 

위와 같이 끝점 기준으로 정렬해 주고 끝을 갱신하며 누적시켜주면 된다.