백준 11067. 모노톤길

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

11067번: 모노톤길

 

우선 주어지는 좌표를 x축 오름차순, x축 같다면 y축 오름차순으로 정렬한다. 

 

이 문제에서 중요한 점은

1. 동쪽에서 서쪽으로 가는 경우는 없다

2. 하나의 y축에서는 한방향으로만 갈 수 있다. (위로 갔다가 다시 아래로 가는 경우는 있을수 없다) 

 

예를들어 위에 주어지는 그림에서 (3,3) 에서 다음길인 (5,3)으로 온 후에는 아래쪽 or 위쪽 한 방향으로 만 쭉 이동할수 있을 것이고, 여기서는 아래 쪽이다.

 

또 다른 예로는 (6,-1)에서 다음 길 (7,-1)로 이동 하고 난 후에도 마찬가지로 아래쪽 or 위쪽 한 방향으로만 갈 수 있고 여기서는 아래 방향으로 갔다. 

만약 (7,-3) 아래로도 길이 있다면 아래로 쭉 이동 한 후에 다음 x좌표로 넘어갈것이다. 

 

3. x에서 x+1로 넘어가는 경우, x+1축에서 가장 먼저 만나는 카페의 위치는 x+1의 y값이 가장 작은 경우 or 가장 큰 경우 둘 중 하나이다.

2번과 마찬가지 논리로 x에서 x+1 축으로 넘어왔다고 했을때, 위 혹은 아래 한 방향으로 만 갈수있다.

처음에 주어지는 좌표를 x축 오름차순, x축 같다면 y축 오름차순으로 정렬했기 때문에 새로운 x축에서 나의 좌표는 같은 x축을 같는 좌표들중 y가 가장 작은값 혹은 가장 큰 값이다.