[BOJ/백준][Gold3] 2836 : 수상 택시 (C++)

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

2836번: 수상 택시

 

 

[난이도] Gold3
[유형] 스위핑

[풀이]
idea : 1) 어차피 M까지 가야하므로 정방향으로 가는 사람들은 고려할 필요가 없다.
2) 반대로 가는 사람들 때문에 돌아가야하는 추가 이동거리가 발생하는데,
5->2, 6->3 이렇게 겹치는 경로가 있는 사람들끼리 묶어서 뒤로 이동하는것이 가장 효율적이다.
3) a>b인 (a,b) 입력에 대해 (b,a) pair로 vector에 저장 뒤 정렬 후,
스위핑을 해주면서 묶인 집합의 길이*2를 답에 더해주면 된다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int N;
ll M;
vector<pair<ll,ll>> v;
int main(){
    scanf("%d%lld",&N,&M);
    for(int i=0;i<N;i++) {
        ll u,r;
        scanf("%lld%lld",&u,&r);
        if(u>r) v.push_back({r,u});
    }
    sort(v.begin(),v.end());

    ll s=v[0].first, e=v[0].second;
    for(auto p : v){
        if(e<p.first){
            M+=2*(e-s);
            s=p.first,e=p.second;
        }else if(e<p.second){
            e=p.second;
        }
    }
    M+=2*(e-s);
    printf("%lld",M);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2836.cpp