백준 22342 계산 로봇

문제

const fs = require("fs");
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = fs.readFileSync(INPUT_FILE).toString().trim().split("\n");
 
const [m, n] = inputs[0].split(" ").map(Number);
const arr = [
  new Array(n + 1).fill(0),
  ...inputs.slice(1).map((e) => [0, ...e.split("").map(Number)]),
];
const resultArr = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
 
const dLoc = [
  [0, -1],
  [-1, 0],
  [1, 0],
];
 
let max = -Infinity;
// 열
for (let i = 1; i <= n; i++) {
  // 행
  for (let j = 1; j <= m; j++) {
    // 첫 줄은 출력값이 자기 가중치 그대로 감
    if (i === 1) {
      resultArr[j][i] = arr[j][i];
    } else {
      const queue = [[j, i]];
      const visited = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
      while (queue.length) {
        const [row, col] = queue.shift();
        for (const [dr, dc] of dLoc) {
          const nr = row + dr;
          const nc = col + dc;
          if (nr < 1 || nr > m || nc < 1 || nc > n || visited[nr][nc]) continue;
          if (Math.abs(j - nr) <= i - nc && nc < i) {
            // 가중치에 출력값을 더한거랑 비교해봄
            resultArr[j][i] = Math.max(
              resultArr[j][i],
              resultArr[nr][nc] + arr[j][i]
            );
            visited[nr][nc] = 1;
            max = Math.max(max, resultArr[nr][nc]);
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
}
 
console.log(max);
 

 
const fs = require("fs");
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = fs.readFileSync(INPUT_FILE).toString().trim().split("\n");
 
const [m, n] = inputs[0].split(" ").map(Number);
const arr = [
  new Array(n + 1).fill(0),
  ...inputs.slice(1).map((e) => [0, ...e.split("").map(Number)]),
];
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
const acc = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
 
let maxVal = -Infinity;
 
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= m; j++) {
    if (i === 1) {
      // 첫 번째 열은 그대로 설정
      dp[j][i] = arr[j][i];
      acc[j][i] = dp[j][i];
      continue;
    }
    for (let k = -1; k <= 1; k++) {
      const prevRow = j + k;
      if (prevRow < 1 || prevRow > m) continue;
      dp[j][i] = Math.max(dp[j][i], acc[prevRow][i - 1]);
      acc[j][i] = dp[j][i] + arr[j][i];
      maxVal = Math.max(maxVal, dp[j][i]);
    }
  }
}
 
console.log(maxVal);
 

const fs = require("fs");
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = fs.readFileSync(INPUT_FILE).toString().trim().split("\n");
 
const [M, N] = inputs[0].split(" ").map(Number);
const inp = Array.from({ length: M + 1 }, () => Array(N + 1).fill(0));
const store = Array.from({ length: M + 1 }, () => Array(N + 1).fill(0));
const print = Array.from({ length: M + 1 }, () => Array(N + 1).fill(0));
 
let ret = 0;
 
for (let i = 1; i <= M; i++) {
  const row = inputs[i].split("").map(Number);
  for (let j = 1; j <= N; j++) {
    inp[i][j] = row[j - 1];
  }
}
 
for (let j = 1; j <= N; j++) {
  for (let i = 1; i <= M; i++) {
    for (let k = -1; k <= 
1; k++) {
      const prevRow = i + k;
      if (prevRow >= 1 && prevRow <= M) {
        store[i][j] = Math.max(store[i][j], print[prevRow][j - 1]);
      }
    }
    print[i][j] = store[i][j] + inp[i][j];
    ret = Math.max(ret, store[i][j]);
  }
}
 
// 결과 출력
console.log(ret);