[Medium] EllysRivers

관찰 1. 각 단계마다 이동할 때는 무조건 서->동 혹은 남->북 혹은 남서->북동 으로 움직여야 한다. 이외의 방향으로 움직인다면 답에서 무조건 손해를 보기 때문이다. 관찰 2. walk를 어디서 얼마만큼 하든 walk를 하는 양의 합이 같다면 답은 변하지 않는다. 섬i에서 A만큼 walk를 하고 섬j에서 B만큼 walk를 한 경우와 섬i에서 A+B만큼 walk를 하고 섬j에서 walk를 하지 않는 경우가 답이 같다는 뜻이다. 관찰 1, 2 를 통해 과정을 다음과 같이 단순화 할 수 있다. - 맨 오른쪽의 섬이 아니라면, walk를 하지 말고 무조건 배를 탄다. 즉, 내가 섬i에 도착한 뒤의 위치가 (i, j) 라면 walk를 하지 말고 (i+1, j+s[i]) 로 배를 타고 바로 이동한다. - 맨 오른쪽 섬에 도착하고 나면 walk로 목적지로 이동한다. - s[0] + s[1] + ... + s[n-1] <= length - s[0] ~ s[n-1] 을 잘 결정해서 전체 이동시간을 최소로 하자! 여기까지 생각했다면 이제 다음과 같은 DP가 자연스럽게 도출된다. D[i][j] = 출발지에서부터 (i, j) 까지 오는데 걸리는 최소 시간 = min( D[i-1][p] + dist((i-1, p), (i, j)) / speed[i-1] , p <= j ) 이 DP를 그냥 단순히 계산하면 O(n * length^2) 이므로 시간내에 계산할 수 없다. 관찰 3. D[i][j] 가 D[i-1][x] 에서 오는 것이 최적이었다고 하자. D[i][j+1] 은 D[i-1][y] 에서 오는 것이 최적이었다고 하자. 그렇다면 항상 x <= y 가 성립해야 한다. 즉, 2개의 경로가 서로 완전히 교차하는 경우는 없다는 것이다. 이는 섬이 3개인 상황을 가정하고 식을 세워서 열심히 풀어보면 증명할 수 있다. 관찰 3 을 이용하면 위의 DP를 빠르게 계산할 수 있다. 분할정복 최적화를 사용하면 O(n * length * lg(length)) sliding window 를 사용하면 O(n * length) 이다. greedy 솔루션도 있다. 관찰 4. (i, j) 에서 (i+1, j+k) 로 이동하는 시간이 전체 시간에 어떻게 기여하는지 생각해보자. 두 지점사이의 직선거리를 L_i(k) 라고 하면, 우선 L_i(k)/speed[i] 만큼이 걸릴 것이다. 그리고 여기서 이동한 시간 만큼 맨 나중의 섬에서 walk를 덜 하기 때문에 전체 시간에서는 k/walk 만큼 줄어든다. 이것을 k에 대한 함수로 나타내면 f_i(k) = L_i(k)/speed[i] - k/walk 이 된다. 2계도함수를 구해보면 k >= 0 일 때 값이 항상 0 이상이므로 이 함수는 볼록함수이다. 우리가 구하려는 답은 sum( f_i(s[i]) ) + length/walk 이다. s[0] = s[1] = .. = s[n-1] = 0 인 상태에서 출발하여 어떤 j를 골라서 s[j] 를 1 증가시키는 식으로 답을 발전시킬 것이다. 이 때, 각 j 마다 s[j] 가 1 증가할 때 답이 얼마나 줄어드는지를 계산한 뒤 그 중 가장 크게 줄어들게 만드는 j를 선택하면 된다. 이 과정을 최대 length 번 반복하면 된다. priority queue 를 이용하면 전체 시간복잡도 O(length * lgN) 이다. 각 f_i 가 볼록 함수이기 때문에 이 greedy는 정당하다.