[백준 14595] 동방 프로젝트(Large) (C++)

14595번: 동방 프로젝트 (Large)

 

x ~ y 사이의 모든 방은 통합해서 하나의 방으로 만든다.

통합하는 순서는 결과에 영향을 주지 않기 때문에 x가 작은 순으로 오름차순 정렬한다.

 

현재 통합한 y 좌표의 최댓값보다 새로 통합할 방의 x좌표가 더 크다면, ((새로운 x) - (이전 y)) 값 만큼 방의 개수가 늘어난다는 뜻이다.

 

만약 새로운 x의 좌표가 현재 y보다 작다면 새로운 방은 더 생기지 않는다.

 

N에서 y의 최댓값을 뺀 값을 마지막으로 더해주면 답을 구할 수 있다.

 

 

문제에서 주어진 3번 예제를 통해 알아보자

 

(1)에서 1-3이 통합된다. 이때 y값 0보다 1이 더 크므로 새로운 방이 (1-0)개 생긴다.

(2)에서 2-4가 통합된다. 이때 x값인 2가 y최댓값 3보다 작기 때문에 y값은 max(3, 4) = 4가 된다.

(3)에서 현재 max(y)보다 큰 x값 5가 들어왔다. 따라서 새로운 방이 (5-4)개 생긴다. 그리고 y = max(y, 8) = 8이 되고 (10-8)개의 방을 마지막으로 더해준다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
 
using namespace std;
 
int N, M;
vector<pii > events;
 
void input(){
    cin >> N >> M;
    int x, y;
    for(int i = 0; i < M; i++){
        cin >> x >> y;
        events.push_back({x, y});
    }
}
 
void solve(){
    sort(events.begin(), events.end());
    
    int ans = 0;
    int x = 0, y = 0;
    
    for(int i = 0; i < M; i++){
        if(events[i].first > y){
            ans += (events[i].first - y);
            x = events[i].first;
            y = max(y, events[i].second);
        }
        else{
            y = max(y, events[i].second);
        }
    }
    ans += (N - y);
    
    cout << ans;
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}