https://www.acmicpc.net/problem/2836
2836번: 수상 택시
상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다.
www.acmicpc.net
[난이도] 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
'Problem-Solving > BOJ' 카테고리의 다른 글
[BOJ/백준][Gold3] 1983 : 숫자 박스 (C++) (0) | 2021.03.01 |
---|---|
[BOJ/백준][Gold3] 17616 : 등수 찾기 (C++) (0) | 2021.03.01 |
[BOJ/백준][Gold5] 2170 : 선 긋기 (C++) (0) | 2021.03.01 |
[BOJ/백준][Gold3] 1132 : 합 (C++) (0) | 2021.03.01 |
[BOJ/백준][Gold3] 1689 : 겹치는 선분 (C++) (0) | 2021.03.01 |