그냥 하는 노트와 메모장

BOJ 1866 - 택배 본문

Solved problems

BOJ 1866 - 택배

coloredrabbit 2019. 3. 27. 08:45

* BOJ 1866 택배 (https://www.acmicpc.net/problem/1866)

[분류 - 다이나믹 프로그래밍]


  구간에 대해 처리를 해야하나 싶었는데 엄청난 수학적 증명 + 다이나믹에 대한 처리가 있어서 소개하고자 합니다.


  1. 우선 정렬을 합시다. 정렬을 해야 거리에 대해서 다음 위치를 계산할 때, 그 이전 거리들을 계산했다는 부분 구조로 만들 수 있습니다.


  2. dp[i] = i 번째 지역까지의 최소값

먼저 구간 [1, N]에 대해 생각해봅시다. 가장 마이너한 0지점에서 트럭만을 이용할 경우 T * pos[i]의 비용이 발생합니다.

반면, 헬기를 이용하는 경우를 생각해봅시다. 최적으로 헬기와 트럭을 배정했다면 하나의 헬기가 담당하는 지역의 위치는 반드시 연속적입니다. 비연속적이라면 비용이 추가적으로 발생하기 때문이죠.


  이제 하나의 헬기 구역에 대해 생각해봅시다. 현재 i번째 지역까지 왔고, i번째를 포함하는 헬기가 어딧는지 알아봅시다. 만약 j번째부터 i번째까지(1 <= j <= i) 하나의 헬기로 담당한다고 가정해봅시다. 구간 [j, i] 중 하나에 반드시 헬기가 하나 떨어질 것이고, 그 경우 중 가장 낮은 비용이 될 때가 이 헬기 구간의 최소값이 됩니다. 


  그럼 그 위치는 어딜까? 단연 하나의 for문을 더 돌면서 구하면 시간 초과가 납니다. 자 모를 땐, 함 그려봅시다.




[그림 - 위치 5개에 대해 구간 a,b,c,d 설정]


만약 1에 헬기가 떨어졌다면 비용=4a+3b+2c+d

만약 2에 헬기가 떨어졌다면 비용=a+3b+2c+d

만약 3에 헬기가 떨어졌다면 비용=a+2b+2c+d

만약 4에 헬기가 떨어졌다면 비용=a+2b+3c+d

만약 5에 헬기가 떨어졌다면 비용=a+2b+3c+4d


가운데에 떨어뜨려야 최소비용이 나오는 건 우연일까? 아니다, 귀납법으로 충분히 증명이 가능하다.



짝수의 경우엔 다음과 같다.


[그림 - 위치 4개에 대해 구간 a,b,c 설정]


만약 1에 헬기가 떨어졌다면 비용=3a+2b+c

만약 2에 헬기가 떨어졌다면 비용=a+2b+c

만약 3에 헬기가 떨어졌다면 비용=a+2b+c

만약 4에 헬기가 떨어졌다면 비용=a+2b+3c


짝수의 경우 가운데 기준 가장 가까운 두 지점에 헬기가 떨어지면 됨을 알 수 있다. 여기까지는 구간 [j, i]의 헬기 위치를 알 게 되었다. 이를 중앙값 center[j, i]라고 하자


다음으론 최소 비용을 구해야 하는데 이게 여간 까다로운 게 아니다.

1. 포함되는 위치가 짝수라면 더 높은 위치의 것을 선택한다.


2. 포함되는 위치가 홀수인 구간 [j, i]에서 [j-1, i]로 범위를 늘린다면 이전 [j, i]에서 계산한 값 cost[j, i] + (center[j, i] - pos[j-1]) * 트럭비용을 하면 해당 헬기 구간의 최소값을 알 수 있다. 여기서는 center[j, i]와 center[j-1, i]가 달라지지 않음을 생각하자.


3. 포함되는 위치가 홀수인 구간 [j, i]에서 [j-1, i]로 범위를 늘린다면 이전 [j, i]에서 계산한 값 cost[j, i] + (center[j, i] - pos[j-1]) * 트럭비용을 하면 해당 헬기 구간의 최소값을 알 수 있다. 여기서는 center[j, i]와 center[j+1, i]가 같으므로 center[j, i]를 왼쪽으로 한칸 이동시켰다고 생각하면 된다.



[그림 - 위치 4개에서 5개로 늘어날 때 중앙 이동]


4. 결론은 추가되는 위치 j-1에 대해서 center[j, i]의 거리 계산만 하면 된다. 직접 계산하면 쉽게 알 수 있는 사실이니 한 15분 정도 투자해서 완벽하게 이해하는 것도 도움이 될 듯 합니다.



정리된 점화식은 다음과 같습니다.



'Solved problems' 카테고리의 다른 글

BOJ 2176 합리적인 이동경로  (0) 2019.08.07
BOJ 17242 Kaka & Bebe  (0) 2019.06.24
FFT 관련 문제들(상대적 쉬움)  (0) 2019.02.23
BOJ 2957 - 이진 탐색 트리 (BST)  (0) 2019.01.01
BOJ 9522 - 직선 게임  (0) 2018.12.17
Comments