[BOJ 2836]

문제 바로가기 : https://www.acmicpc.net/problem/2836
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

BOJ 2170에서 썼던 아이디어를 응용하는 문제다.
상근이는 0에서 M까지 이동하는데 이 방향을 순방향이라고 하자.
순방향으로 가는 승객은 신경쓸 필요가 없다. M으로 가면서 중간에 내려주면 되기 때문에 추가로 이동하지 않는다.
신경쓸 부분은 역방향으로 가는 승객이다. 원래 갈 거리가 M이었는데 승객이 역방향으로 가면 그 거리의 2배를 이동해야 한다.

근데 역으로 가는 승객들이 많다고 생각해볼 필요가 있다. 이 승객들의 경로가 겹칠 수도 있다!
이렇게 역방향으로 이동하는 승객들의 경로만 모아놓고 정렬하면 BOJ 2170와 다를게 없다.
역으로 이동하는 거리를 구한 후, 2배를 해주고 M에 더해주면 답이 된다.