DP로 어떻게 푸신다는 건지 언급이 없어 뭐라 말을 드리기가 어렵네요.

이 문제의 풀이는 단순하게 (k+1번째 사건까지의 최적 경로)= (k번째 사건까지의 최적 경로)+(두 차 중 더 가까운 것 움직이기)

가 아닙니다.

찾아보니, 보통 귀류법으로 증명하는 거 같은데, 그러면 여기서 일반성을 잃지만,

f(n - 1)에 의해서 f(n)를 구하는 법을 특정 방법 하나로 제한시켜서 진행시켜보면,

일단 f(n)을 n개의 지점을 방문하는 데 이동하는 거리의 합이 최소가 되도록 하는 답과 관련된 모든 필요 정보가 담겨 있다고 해봅니다.

그 중에서 필요할 것 같은 정보면 좀 추리면, f(n) = (거리, A차 마지막 위치, B차 마지막 위치)로만 제한해봅니다.

그리고 f(n - 1)에 의해서 f(n)을 구하는 방법을 다음과 같이 정해봅니다. (f의 정의)

f(n)[거리] = f(n - 1)[거리] + min(dist(p_A, p_n), dist(p_B, p_n))이고, 여기서 p_A, p_B, p_n차례대로 A차의 마지막 위치, B차의 마지막 위치, n번째 지점입니다.

f(n)[A차 마지막 위치], f(n)[B차 마지막 위치]도 어렵지게 않게 업데이트할 수 있습니다.

자, 그러면 어떤 p_n = (x_n, y_n)이 존재하여, f'(n)[거리] < f(n)[거리]이 가 성립하게 하는 f'이 존재하는가 인데, 흠 여기서 어떻게 하죠  ㅋㅋㅋ흠....

f'이 반드시 만족해야는 조건 중에는 흠, n개의 지점을 모두 순차 방문해야 되는 것인데, 이 조건을 만족하면 거리가 갖는 최솟값을 어떻게 표현해야 다음 단계로 넘어 갈 수 있을 거 같네요..

아 그게 아니군요!

게시판 글 보다가, 저렇게 해서 풀렸다는 사람이 있길래, 그런가보다 했는데 아니었군요...

빠른 답변 감솨합니다! 조금 더 고민해보고 머리 너무 아프면 다시 도움 청할게요