문제
접근
너무 어려웠다..
사건이 N개 발생했을 때 이동할 수 있는 경우의 수는 2^N개가 된다.
일단 DP인건 확실한데,, 어떻게 구성할지 감도 안잡힌다.
결국 종이에 N을 작게해서 경우의 수들을 그려봤다.
이 때 좌표를 생각하지말고 그냥 사건의 idx로 생각하면 좀더 쉬워진다.
좌표는 나중에 다시 생각하자..
1번 사건, 2번 사건…. N번 사건 타고 들어가면서 경찰차1,2에게 맡기는 경우의 수들을 그려보자.
경찰차 1,2를 편의상 x,y라고 하겠다.
xxx
xxy
xyx
xyy
yxx
yxy
yyx
yyy
사건 3개일 때 경우의 수다.
이거로 뭘할까…
거꾸로 생각해보니까 알듯말듯하다.
3번 사건에 x가 갔다고하면 x는 3번 사건이 발생한 좌표에 있다.
2번 사건에도 x가 갔다면 x는 2번 사건이 발생한 위치에 있겠지.
그럼 ?xx에서 ?는 일단 빼고 xx 사이의 이동거리는 2번사건에서 3번사건 사이의 거리이다.
근데 이 ?xx는 xxx, yxx가 있고, 이때 2,3번 사건의 xx는 앞이 무엇이든 동일하다!!
조금 감이 잡혔다. dp에 저걸 넣으면 되겠구나!
사건의 개수가 늘어날수록 저렇게 겹치는 부분이 많이 생길거고, 그걸 매번 계산하지 않고 가져다쓰면 된다.
근데 여전히 저걸 dp에 어떤식으로 넣어줄지 모르겠다.
일단 사건을 중심으로 생각해야 한다.
x가 사건1을 해결 했을 때는 x의 기존위치에서 사건1까지 거리 + (사건2~N까지의 최소)
y가 사건1을 해결 했을 때는 y의 기존위치에서 사건1까지 거리 + (사건2~N까지의 최소)
한 사건에 대한 경우의 수는 두 가지가 전부이다.
x가 마지막으로 해결한 사건 번호, y가 마지막으로 해결한 사건 번호를 가지고 있으면 될거같다.
DP(i, j) = x가 마지막으로 해결한 사건이 i이고, y가 마지막으로 해결한 사건이 j일 때 남은 사건의 최소 거리??
그럼 min(distance(x, i) + DP(x+1, y), distance(y, j) + DP(x, y+1)) 이런 식인가??
구현해봐야겠다.
- 사건의 좌표들을 하나의 리스트에 저장해서 해결하려다가 망했다.
처음 시작 지점을 넣어줘야 한다.
그니까 사건1,2,3…이 있다면
사건의 리스트는 경찰차의 시작위치를 사건0이라고 생각하고, 사건 0,1,2,3,4로 해줘야 편해진다.
근데 경찰차1,2의 시작점이 다르다…
뭔가 조건을 주면 될거 같기도 한데,, 잘 모르겠어서 그냥 리스트 두개로 만든다.. 너무 낭비같지만..
다음 사건이 발생하는 위치까지의 거리를 경찰차1, 2번에 대해서 각각 구해준다.
각각의 거리를 dis1, dis2, 다음 사건을 next라고 할 때,
dp(car1, car2)는 다음과 같다.
dp(car1, car2) = min(dis1 + dp(next, car2), dis2 + dp(car1, next))
이제 문제는 역추적이다.
재귀 형태로 탑다운 방식을 사용했더니(바텀업은 어떻게할지 감도 안잡힘, 탑다운은 재귀아니면 어떻게 하는지 모름..ㅎ) 역추적을 못하겠다.
역추적하는 방법을 찾아보고나서야 풀었다.
역추적 자체는 생각보다 간단했다.
DP를 구할 때처럼 똑같이 따라가는거다.
근데 우리는 앞에서 정답을 구하면서 dp를 모두 채워놨기 때문에 한 사건에 대해 추적하는데 O(1)이 걸린다.
즉, 역추적 자체는 사건이 m개 있을 때 O(m)이면 해결이 가능하다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def findDP(dp, case1, case2, car1, car2, n):
if dp[car1][car2] != -1:
return dp[car1][car2]
if car1 == n or car2 == n:
return 0
nextCase = max(car1, car2) + 1
car1Dis = abs(case1[car1][0] - case1[nextCase][0]) + abs(case1[car1][1] - case1[nextCase][1])
car2Dis = abs(case2[car2][0] - case2[nextCase][0]) + abs(case2[car2][1] - case2[nextCase][1])
result1 = car1Dis + findDP(dp, case1, case2, nextCase, car2, n)
result2 = car2Dis + findDP(dp, case1, case2, car1, nextCase, n)
dp[car1][car2] = min(result1, result2)
return dp[car1][car2]
def pathPrint(dp, case1, case2, car1, car2, n):
if car1 == n or car2 == n:
return 0
nextCase = max(car1, car2) + 1
car1Dis = abs(case1[car1][0] - case1[nextCase][0]) + abs(case1[car1][1] - case1[nextCase][1])
car2Dis = abs(case2[car2][0] - case2[nextCase][0]) + abs(case2[car2][1] - case2[nextCase][1])
result1 = car1Dis + dp[nextCase][car2]
result2 = car2Dis + dp[car1][nextCase]
if result1 < result2:
print(1)
pathPrint(dp, case1, case2, nextCase, car2, n)
else:
print(2)
pathPrint(dp, case1, case2, car1, nextCase, n)
if __name__ == "__main__":
n = int(input())
m = int(input())
dp = [[-1]*(m+2) for _ in range(m+2)]
startLocCar1 = [(1,1)]
startLocCar2 = [(n,n)]
case = [tuple(map(int, input().split())) for _ in range(m)]
case1 = startLocCar1 + case
case2 = startLocCar2 + case
print(findDP(dp, case1, case2, 0, 0, m))
pathPrint(dp, case1, case2, 0, 0, m)