문제

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

입력

첫 번째 줄에 체크포인트의 수 N이 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x좌표, 두 번째 정수는 y좌표이다. (-1000 ≤ x, y ≤ 1000)

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

출력

젖소 박승원이 체크포인트 1개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

예제 입력

4
0 0
8 3
11 -1
10 0

예제 출력

14

내가 했던 풀이 방법

• 이동할 체크포인트, 현재 체크포인트, 건너뜀 여부, 현재까지의 거리를 이용하여 DFS로 풀이하였으나 시간초과 발생 -> N (3 ≤ N ≤ 100000) 때문

1. N×2의 배열을 만들고 Infinity로 채워준다. (dp[n][0]은 건너뛰지 않고 이동했을 때의 거리가 저장되어 있고, dp[n][1]은 건너뛰었을 때의 이동거리이다. 예를 들어 dp[2][1]은 첫 번째에서 세 번째로 건너뛴 거리가 저장되어있다. n은 0부터 시작한다.)
2. 1번 체크포인트는 무조건 지나야 하고 순서대로 이동하므로 dp[0][0]과 dp[0][1]은 0으로 바꿔준다.
3. 0부터 N-1까지 i를 1씩 증가시키면서 건너뛰지 않았을 때, 건너뛸 때, 이미 건너뛰었을 때를 계산하여 dp에 넣어준다. 마지막 체크포인트는 무조건 지나야 하므로 건너뛸 수 없다. 그러므로 건너뛸 때는 i+2가 N보다 작은 상태여야 한다. (해당 dp는 같은 요소에 또 다시 접근할 수가 있다. 그러므로, 최단 거리를 찾기 위해 Math.min을 이용하여 기존 dp에 있는 값과 새로 들어올 값을 비교하여 더 작은 값을 dp에 저장해주어야 한다. 그러므로, 배열의 초기값을 Infinity로 채워주었다.)
4. N-1번째(마지막 체크포인트) dp 값 중 더 작은 값을 출력해준다.

코드

const fs = require('fs');
let [N, ...checkPoints] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
let dp = Array.from({ length: N }, () => Array(2).fill(Infinity));

function Manhattan(x, y) {
  x = x.trim().split(' ').map(Number);
  y = y.trim().split(' ').map(Number);

  return Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1]);
}

dp[0][0] = 0;
dp[0][1] = 0;

for (let i = 0; i < N - 1; i++) {
  dp[i + 1][0] = Math.min(dp[i + 1][0], dp[i][0] + Manhattan(checkPoints[i], checkPoints[i + 1]));
  if (i + 2 < N) {
    dp[i + 2][1] = Math.min(dp[i + 2][1], dp[i][0] + Manhattan(checkPoints[i], checkPoints[i + 2]));
  }
  dp[i + 1][1] = Math.min(dp[i + 1][1], dp[i][1] + Manhattan(checkPoints[i], checkPoints[i + 1]));
}

let shortest = Math.min(dp[N - 1][0], dp[N - 1][1]);

console.log(shortest);

회고

DP로 풀어야 할 것 같은 문제를 보면 꼭 DFS로 풀게되는 습관이 있다. DP 자체가 떠올리기 쉽지 않기도 하고, 아직은 어렵게만 느껴져서 DP 문제야? 그럼 딴 걸로 먼저 풀고 안 되면.... 이렇게 생각하는 것 같다. 그래서 그런지 다른 유형들보다 DP 문제는 아직도 초반에 막히는 게 있는 것 같다. 이번에도 DFS로 바꿔서 풀다가 (심지어 N 제한을 보고도 안 되겠다는 걸 알면서도 풀었다..) DP로 코드를 바꾸려고 하니 어떻게 시작할지를 계속 고민한 것 같다. 결국 GPT 선생님의 조언을 받았다...ㅎ.... 구현 알고리즘 자체는 내가 생각했지만 결과적으로 코드가 굴러가도록 한 건 GPT 선생님인 것이다.. 참....... 씁쓸한 것 같다. DP를 어떻게 하면 잘 풀게 될 수 있을까...