스위핑. [2836]

[1. 문제 설명]

0번 위치에서 M번 위치까지 가려고 하는데,

이 사이에 A 위치에서 B 위치로 이동하려는 사람들을 운송해야 할 때,

이동해야 하는 최소거리를 구한다.

[2. 풀이 접근]

A < B 인 경우에는 따로 신경쓰지 않아도 된다.

운송자가 가려는 방향에 있기 때문이다.

문제는 A > B 인 경우로 운송자가 가려는 방향과 반대되는 경우이다.

검정색 화살표는 운송자가 이동하는 방향이고

빨간색 화살표는 승객이 이동하려는 방향이다.

이 빨간색 화살표들을 최소 거리로 이동하면 된다.

2번 승객을 처리하고, 3번 승객을 처리하고, 마지막으로 1번 승객을 처리하는 것이 아니라

1번 승객을 먼저 처리하고, 2번 승객을 태우고, 3번 승객을 태운 다음

3번 승객을 먼저 내리고 2번 승객을 먼저 내리게 하면 된다.

본질은 이 문제와 유사하다.

다만, 역방향으로 이동하고 다시 정방향으로 움직여야 하기 때문에,

역방향 거리의 두배 만큼을 출력하려는 값에 더해주어야 한다.

시간복잡도는 정렬이 지배적이므로

O(NlogN) 이다.

[3. 코드]

test_kernelv2