import sys
input = sys.stdin.readline
def DFS(x1,x2):
DP[x1][x2] = 0
M = max(x1,x2)+1
for next in range(M,N-1):
if not graph1[x1][next]:
break
if DP[next][x2]==-1:
DFS(next,x2)
DP[x1][x2] += DP[next][x2]
for next in range(M,N-1):
if not graph2[x2][next]:
continue
if DP[x1][next]==-1:
DFS(x1,next)
DP[x1][x2] += DP[x1][next]
DP[x1][x2] += int(graph1[x1][-1]==graph2[x2][-1]==1)
DP[x1][x2] %= 1000
N = int(input())
data = [[*map(int,input().split())] for i in range(N)]
graph1,graph2 = [[[0]*N for i in range(N)] for i in range(2)]
for i in range(N):
x,d,p = data[i]
for j in range(i+1,N):
if data[j][0]>x+d:
break
graph1[i][j] = 1
if p:
for j in range(i-1,-1,-1):
if data[j][0]<x-d:
break
graph2[j][i] = 1
DP = [[-1]*N for i in range(N)]
DFS(0,0)
print(DP[0][0])
DFS+DP로 해결하였다.
처음에는 풀이가 전혀 생각나지 않는 문제였다. 그러다가 NP-hard [백준 9520번] NP-hard (Python3) (tistory.com) 문제를 풀었는데, NP-hard 문제가 경찰차 [백준 2618번] 경찰차 (Python3) (tistory.com) 문제와 사실상 같은 문제라는 사실을 알게되었다.
즉, "1번 지점에서 N번 지점까지 갔다가 돌아오기" 를 "1번 지점에서 N번 지점까지 두 번 이동하기" 로 치환할 수 있다는 것이다. 이 사실을 알고 나자 '어 그럼 이걸 이용하면 저번에 봤던 공주 구하기 문제도 비슷하게 풀 수 있겠는데?' 하는 생각이 들었고, 실제로 해결할 수 있었다.
풀이를 설명하면,
1. graph1, graph2를 만든다. graph1은 현재노드에서 오른쪽으로 뛰었을 때 이동가능한 노드를 1로 표시한 인접행렬, graph2는 각 노드에서 왼쪽으로 뛰었을 때, 현재 노드에 '도착'가능한 경우 1로 표시하는 인접행렬이다. (출발, 도착 주의)
2. DP[x1][x2]는 x1를 밟으면서 N에 도착하고 x2를 밟으면서 돌아오는 경우의 수이다. 다른말로 하면 두 사람이 0에서 출발해서 한명은 x1, 한명은 x2에 있을 때 둘 다 N에 도착하는 경우의 수이다.
3. x1은 graph1을 x2는 graph2을 통해 이동한다. 이때 이동할 때에는 max(x1,x2)보다 큰 지점으로만 이동할 수 있다. (중복방지)
4. x1과 x2 모두 N으로 갈 수 있으면 +1을 한다.
5. DFS를 하여 DP[0][0]를 출력한다.
경찰차 문제와 풀이가 거의 유사하다. "갔다가 돌아오기 = 두번 이동하기" 라는 특성을 알면 쉽게 해결할 수 있는 문제였다.
오늘의 교훈) 왕복이동은 두번 이동하는것으로 치환할 수 있다.