백준 문제풀이/Nodejs
[백준][dp] 1937 욕심쟁이 판다 NodeJs 구현
꽁이꽁설꽁돌
2025. 1. 9. 17:55
728x90
반응형
목차
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);
반응형