99클럽 코테 스터디 14일차 TIL - 진우의 달 여행 (Small) (dp)

문제: https://www.acmicpc.net/problem/17484

접근방식

• dp[i][j][d]를 i행 j열에서 이전 이동 방향이 d일 때의 최소 연료 소비량이라고 정의
• d는 0: 왼쪽 아래(↙), 1: 아래(↓), 2: 오른쪽 아래(↘) 로 구분
• 같은 방향을 연속해서 사용할 수 없기 때문에 이전 방향(prevD)과 현재 방향(d)이 같을 때는 건너뜀

구현

const fs = require("fs")
const [[n, m], ...map] = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(str => str.split(" ").map(Number))

const dx = [-1, 0, 1]
const dp = Array.from({ length: n }, () => Array.from({ length: m }, () => Array(3).fill(Infinity)))

for (let j = 0; j < m; j++) {
  for (let d = 0; d < 3; d++) {
    dp[0][j][d] = map[0][j]
  }
}

for (let i = 1; i < n; i++) {
  for (let j = 0; j < m; j++) {
    for (let d = 0; d < 3; d++) {
      const prevJ = j + dx[d]
      if (prevJ < 0 || m <= prevJ) continue
      for (let prevD = 0; prevD < 3; prevD++) {
        if (d === prevD) continue
        dp[i][j][d] = Math.min(dp[i][j][d], dp[i - 1][prevJ][prevD] + map[i][j])
      }
    }
  }
}

const result = Math.min(...dp[n - 1].flat())
console.log(result)