[BOJ] 13303번: 장애물

https://www.acmicpc.net/problem/13303

첫 번째로, 가로방향 이동거리는 동일하기 때문에(서쪽으로 이동할 일은 없으므로) 위, 아래로 얼마나 이동하는지만 생각하면 됩니다.

두 번째로, 장애물을 x좌표 기준으로 정렬해두고 그 x좌표까지 도달할 수 있는 도착점들을 전부 기억해두었다고 할 때, 그 장애물의 yl~yr 범위에 있는 도착점을 지우고 yl, yr을 새로운 도착점에 추가할 수 있습니다. 이 때 set을 이용해 NlgN에 수행 가능합니다.

이 과정을 끝내고 나면 가능한 모든 도착점이 set에 남아있기 때문에 거기서 최솟값을 구하고 나면 답을 알 수 있습니다. 이게 초등부 문제라니 요새 초딩들 대단하네요.

https://github.com/blisstoner/BOJ/blob/master/13303.cpp