🎲 백준 11048번 이동하기

백준 11048번

💡 크기가 Y+1,X+1인 dp배열을 만들어주고 dp[1][1]부터 차례대로 현위치까지의 사탕 최댓값을 구해준다.
💡 dp[i][j]의 이전 위치는 dp[i-1][j],dp[i][j-1],dp[i-1][j-1]이다. 이 중 최댓값을 고르고 현위치의 사탕 개수(input[i-1][j-1])를 더해주면 dp[i][j]의 값이 된다.
💡 dp크기를 Y+1, X+1로 해준 이유는 0으로 채워 미로를 벗어났을 경우를 쉽게해주기 위해서이다.

코드

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

const [Y, X] = input.shift().split(" ").map(Number);
input = input.map((item) => item.split(" ").map(Number));

const dp = Array.from(new Array(Y + 1), () => new Array(X + 1).fill(0));

for (let i = 1; i < Y+1; i++) {
  for (let j = 1; j < X+1; j++) {
    dp[i][j] =
      Math.max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + input[i-1][j-1];

  }
}

console.log(dp[Y][X]);