IOI' 2004 Hermes

헤르메스의 심부름

그리스 신들이 사는 현대식 도시에는 길거리의 도로들이 X, Y 축에 평행하며 정수 좌표로 된 격자 형태로 배열되어 있다. 임의의 정수 Z에 대해, y=Z로 표현되는 수평 도로가 있고, x=Z로 표현되는 수직 도로가 있다. 그래서 정수로 구성된 좌표는 수평· 수직 도로가 만나는 교차로가 된다.

날씨가 더우면 신들은 바로 이 교차로들 중 어디엔가 있는 카페테리아에 따로 따로 흩어져 쉰다. 신들의 심부름꾼인 헤르메스는 이날도 길거리의 도로만 이용하여 이동한 뒤, 여러 카페테리아에 흩어져 있는 신들에게 메시지를 부지런히 전달한다. 한 메시지는 한 신만을 대상으로 하고 있으나, 전달 과정에서 메시지가 다른 신이 있는 지점을 통과하더라도 상관은 없다.

헤르메스는 초기에 원점 (0, 0)에 있다. 전달 순서라는 개념이 존재하기 때문에 헤르메스는 자신에게 가까운 곳부터가 아니라 먼저 소식을 전해야 하는 신에게 먼저 메시지를 전달해야 한다. 단, 메시지는 직진하는 광자를 발사하는 방식으로 전하기 때문에, 헤르메스는 목적지인 신이 있는 곳과 x 위치가 같거나 y 위치가 같은 지점까지만 가면 된다. 전해야 하는 메시지를 모두 전하면 헤르메스의 임무는 끝난다.

가야 하는 카페테리아들의 위치를 입력으로 받아, 헤르메스가 각 지점들을 순서대로 방문하며 메시지를 전달하는 데 필요한 최소한의 이동량을 계산하는 프로그램을 작성하시오.

입력 (hermes.in)

첫째 줄에는 전해야 하는 메시지의 총 개수 N이 있다. 그리고 다음 N줄에는 각 메시지를 전하기 위해 방문해야 하는 카페테리아가 교차로의 어느 위치에 있는지, 그 좌표가 한 줄에 하나씩, X, Y 축 순으로 들어있다. 모든 테스트 케이스에 대해 1≤ N ≤ 20000, -1000≤ 카페테리아의 X, Y좌표 ≤ 1000이다. 또한, 전체 테스트 케이스 중 절반은 1≤ N ≤ 80이다.

5
8 3
7 -7
8 1
-2 1
-2 1
6 -5

출력 (hermes.out)

최소의 이동 거리를 나타내는 숫자 하나를 한 줄에다 출력한다.

11

(0, 0)에서 (8, 0), (7, 0), (7, 1), (6, 1)의 순으로 이동하면, 이동량이 최소인 11이 되면서 위의 다섯 곳에 모두 순서대로 메시지를 전할 수 있다.

번역출처 :  http://moogi.new21.org/ioi16.htm#2/

Observation

i번째 심부름 위치를 (xi,yi)으로 하자.

i번째 심부름을 해결 할수 있는 위치는 (x,yi) , (xi,y) 이다. (x,y 는 임의의 값)

i번째 심부름을 해결하고 i+1심부름을 해결 할 수 있음으로 i번째 심부름을 해결할수 있는 모든 위치에서의 최소시간을 구하고, 이를 토대로 i+1사건을 해결할수 있는 모든 위치의 최솟값을 구한다. 

X[j] = i번째 심부름을 처리하기위해 좌표 (j,yi) 에 도달하기 위한 최솟값

       이는 i-1사건을 처리하고 나서 (j,y[i-1])위치에 있는 해르메즈를 (j,yi)로 이동시킬수 있고,

   i-1사건을 처리하고 나서 (x[i-1],yi)위치에 있는 헤르메즈를 (j,yi)로 이동시킬수 있다.

Y[j] = i번째 심부름을 처리하기위해 좌표 (xi,j) 에 도달하기 위한 최솟값

       이는 i-1사건을 처리하고 나서 (x[i-1],j)위치에 있는 헤르메즈를 (xi,j)로 이동시킬수 있고,

            i-1사건을 처리하고 나서 (xi,y[i-1])위치에 있는 헤르메즈를 (xi,j)로 이동시킬수 있다.

위와같이 Dynamic 정의를 세우고 코딩한다면

시간복잡도 O(c*N) ( c는 상수로 여기서는 좌표범위인 2000  )

공간복잡도 O(N)이다