백준 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번 집으로 가기 위해서 이동해야 하는 거리의 최솟값을 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : Sweep line

(0) 생각

 모든 사람은 두 부류로 나눌 수 있습니다.

    1. 정방향으로 가는 사람 ( 타는 위치 <= 내리는 위치 )

    2. 역방향으로 가는 사람 ( 타는 위치 > 내리는 위치 )

 기본적으로 상근이는 0번 집에서 M번 집을 갈 것입니다. 즉, 애초에 M을 이동해야 합니다.

 따라서 1 유형의 사람은 이 과정에서 자연스레 타고 내리게 됩니다.

 문제는 2 유형의 사람이겠죠.

 2 유형의 각 사람들을 효율적으로 묶어서 이동시키는 일에 대해 생각해 봐야합니다.

 예를 들어 위 그림과 같이, 두 명의 2유형 사람 6 -> 2 , 8-> 3 이 있다고 생각해봅시다.

 두 명을 따로 데려 주고 오면, 2*(6-2) + 2*(8-3) = 18 을 이동해야 합니다. 

 (내려주고 다시 원 위치로 와야 하므로 2를 곱해야 함을 생각해 줍니다.)

 하지만 위와 같이 8을 데려다 주면서 6을 태우고 8을 3에 내려주고, 6을 2에 내려주면

 2*(8-2) = 12 만 이동하면 됩니다.

 따라서

    1. 유형의 사람을 타는 곳이 큰 순으로 정렬한 뒤 탐색을 하면서

    2. 먼저 태운 사람이 내리기 전, 다음 사람이 합승 가능하다면 합승 시킵니다.

       이때 내려주는 곳은 원래 목적지와, 새로 탄 사람의 목적지 중 작은 곳으로 최신화합니다.

(1) 코드 16~22

 입력 받으면서 역방향 사람만 따로 저장해줍니다.

(2) 코드 24~47

 과정(0)의 생각처럼, 애초에 이동해야 하는 M 거리에 역방향 사람들을 효율적으로 묶어서 이동 시킨 거리를 추가한 것이 답입니다.

 역방향 사람을 타는 곳이 큰 순으로 정렬하여, 합승시킬 수 있으면 합승시켜서 추가거리를 구합니다.