[백준 1520번] DP[다이나믹 프로그래밍] - 내리막길

✨ 문제 ✨

✨ 정답 ✨

const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();

// const fs = require('fs'); 
// let input = fs.readFileSync("/dev/stdin").toString().trim();

// 답지 풀이
input=input.split('\n')
const [M, N] = input.shift().split(' ').map(Number);
const map = input.map(v => v.split(' ').map(Number));
const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const dp = [...Array(M)].map(() => Array(N).fill(-1));
dp[M - 1][N - 1] = 1;

const dfs = (x, y) => {
  if (dp[x][y] !== -1) {
    return dp[x][y];
  }
  let count = 0;

  for (let i = 0; i < 4; i++) {
    const nx = x + offset[i][0];
    const ny = y + offset[i][1];
    if (
      nx >= 0 && nx < M && ny >= 0 && ny < N
        && map[x][y] > map[nx][ny]
    ) {
      count += dfs(nx, ny);
    }
  }

  dp[x][y] = count;
  return count;
};

console.log(dfs(0, 0));





// 실패한 풀이
// input = input.split('\n')

// const [N, M] = input.shift().split(' ').map((el) => +el)
// let array = [];
// for (let i = 0; i < N; i++) {
//     array.push(input[i].split(' ').map((el) => +el))
// }
// console.log(array)

// let dp = Array.from({ length: N }, () => new Array(M).fill(1));
// dp[0][0] = 1;

// for (let i = 0; i < N; i++) {
//     for (let j = 0; j < M; j++) {
//         if (i > 1 && j > 1 && array[i - 1][j - 1] > array[i][j]) {
//             dp[i][j] += dp[i - 1][j - 1]
//         }
//         if (i > 1 && j > 1 && array[i][j - 1] > array[i][j]) {
//             dp[i][j] += dp[i][j - 1]
//         }
//         if (j < M - 1 && array[i][j + 1] > array[i][j]) {
            
//             dp[i][j] += dp[i][j + 1]
//         }
//         if (i < N - 1 && dp[i + 1][j] > dp[i][j]) {
//             dp[i][j] += dp[i + 1][j]
//         }
//     }
// }

// console.log(dp)

🧵 참고한 정답지 🧵

https://tesseractjh.tistory.com/201

💡💡 기억해야 할 점 💡💡

어렵다.