Node.js) 백준 11048번: 이동하기

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

11048번: 이동하기

 

 

 

memo[i][j] 는 (i,j)까지 이동했을 때 얻을 수 있는 사탕의 최대 개수

조건식

memo[i][j] = max(memo[i][j - 1], memo[i - 1][j], memo[i - 1][j - 1]) + (i,j)에 있는 사탕의 개수


초기값
memo[n][m] = 0;  (0<=n<=N , 0<=m<=M)

 

 

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, M] = input.shift();

let memo = Array.from(Array(N + 1), () => Array(M + 1).fill(0));

for (let i = 1; i <= N; i++) {
	for (let j = 1; j <= M; j++) {
		memo[i][j] = Math.max(memo[i][j - 1], memo[i - 1][j], memo[i - 1][j - 1]) + input[i - 1][j - 1];
	}
}

console.log(memo[N][M]);