[백준][dp] 1937 욕심쟁이 판다 NodeJs 구현

     

목차

 

https://www.acmicpc.net/problem/1937

문제

 

 

문제 구현 방향

dfs bfs로 풀면 유다희.. dp로 풀어야 하는 문제이다.

이전 방문의 누적을 한 값을 더해주자 dp는 여전히 어렵다..

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");


let board = [];
let idx = 1;
let N = +input[0];

let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];
let dp = Array.from({ length: N }, () => Array(N).fill(0));
let ans = 0;

while (idx < input.length) {
  let p = input[idx].trim().split(" ").map(Number);
  board.push(p);
  idx++;
}

function moving(x, y) {
  if (dp[y][x]) return dp[y][x];
  dp[y][x] = 1;
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
    if (board[ny][nx] < board[y][x]) {
      dp[y][x] = Math.max(dp[y][x], moving(nx, ny, dp) + 1);
    }
  }
  return dp[y][x];
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    ans = Math.max(ans, moving(i, j, dp));
  }
}
console.log(ans);