[C++]백준 - 2836번 문제

2836번: 수상 택시 (acmicpc.net)

2836번: 수상 택시

 

2836번 : 수상택시

---

상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다.

상근이는 0번 집에 살고 있고, 보트를 이용해서 사람들을 운송하는 일을 하고 있다.

오늘은 저녁때까지 M번 집으로 가야한다. 상근이는 M번 집으로 가는 길에 사람들을 태워주려고 한다.

오늘 상근이의 수상 택시를 타려고 하는 사람은 총 N명이다. 상근이는 각 사람들이 탑승할 위치와 목적지를 알고 있다. 상근이의 보트는 매우 커서 N명 모두 보트에 태울 수 있다.

예를 들어, 사람 A가 2번 집에서 8번으로 가려고 하고, B가 6에서 4로 가려고 하는 경우를 생각해보자. 상근이는 0번 집에서 시작해서, 2번에서 A를 태우고, 6번에서 B를 태울 것이다. 그 다음 4로 돌아가 B를 내려주고, 8번에서 A를 내려다준다. 그 다음에 원래 상근이가 가려고 했던 M번 집으로 가면 된다.

상근이가 모든 사람을 데려다주고, M번 집으로 가기 위해서 이동해야 하는 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N과 M이 주어진다. (N ≤ 300,000, 3 ≤ M ≤ 109)

다음 N개 줄에는 각 사람이 상근이의 수상 택시를 타는 위치와 목적지가 주어진다. 모든 숫자는 0과 M 사이이다.

 

 

출력

---

첫째 줄에 상근이의 이동 거리의 최솟값을 출력한다.

 

 

 

---

 

생각해 볼 점

---

이 문제는 역방향 진행에만 스위핑 기법을 이용하면 됩니다.

 

1. 어차피 0 -> M은 고정적으로 가야합니다.

2. 0 -> M 방향을 가진 사람들은 모두 무시해도 됩니다.

3. 역방향 (M -> 0)의 방향으로 진행하는 사람들에게 스위핑 기법을 이용해 거리를 더해줍니다.

 

 

위와 같이 동일 방향으로 진행하는 경우,

 

2 -> 10으로 가는 승객을 태우고 가던지 그냥 가던지 최종 거리는 10으로 같습니다.

 

 

반면, 0 -> 10으로 진행 중, 6 -> 2로 가는 승객을 만날 경우엔 되돌아가야 하므로,

 

거리가 늘어납니다.

 

그것도 돌아갔다가 다시 오는 만큼 늘어나므로, 4 * 2 = 8의 거리 만큼 더 가야합니다.

 

따라서, 역방향으로 가는 모든 정점 정보만 고려하여 스위핑 알고리즘을 적용한 후,

 

계산된 거리의 2배를 해서 더해주면 정답입니다.

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool sorting(pair<int, int> A, pair<int, int> B)
{
	return A.first > B.first;
}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	long long total_dist = M;
	vector<pair<int, int>> rev_direction;
	for (int i = 0; i < N; i++)
	{
		int dep, des;
		scanf("%d %d", &dep, &des);
		if (des < dep) rev_direction.push_back({ dep, des });
	}

	sort(rev_direction.begin(), rev_direction.end(), sorting);

	//스위핑
	int A = M, B = M;
	for (pair<int, int> p : rev_direction)
	{
		if (p.first < A)
		{
			total_dist += 2 * (long long) (B - A);
			B = p.first;
		}
		if (p.second < A) A = p.second;
	}

	total_dist += 2 * (long long)(B - A);
	printf("%lld", total_dist);
	return 0;
}

 

그 외

---