백준 11048 < 이동하기 > JavaScript

📍문제 링크

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

11048번: 이동하기

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

사탕이 R행 C열의 좌표평면에 몇 개씩 놓여져 있다

1행 1열에서 출발하여 R행 C열 까지 이동한다고 할때 경로를 지나며 획득할 수 있는 사탕의 최대 갯수를 구하면 된다

이때, 이동할 수 있는 방향은 3시 방향, 5시 방향, 6시 방향의 3개이다

 

R+1 * C+1 크기의 memoization 이차원 배열을 그리고, 직전에 올 수 있는 위치들의 최댓값과 현재 위치를 더하며 DP를 구현하면 된다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [r, c] = input.shift().split(" ").map(Number);
  const board = input.map((el) => el.split(" ").map(Number));
  const memo = Array.from({ length: r + 1 }, (_) =>
    Array.from({ length: c + 1 }, (_) => 0),
  );
  for (let i = 1; i <= r; i++) {
    for (let j = 1; j <= c; j++) {
      memo[i][j] =
        board[i - 1][j - 1] +
        Math.max(memo[i - 1][j - 1], memo[i - 1][j], memo[i][j - 1]);
    }
  }
  console.log(memo[r][c]);
});