[백준] 1932. 정수 삼각형 (자바스크립트/javascript/js/node.js/동적계획법/동적프로그래밍/다이나믹프로그래밍)

 

 

문제를 풀기 위한 아이디어

삼각형의 각각 n번째 줄을 행이라고 하고 그 행에서 하나의 요소들을 열이라고 둔다면

같은 행 안에서 가장 첫 열과 가장 끝 열을 제외하고 중간에 있는 요소들은 겹친다. 즉 중복해서 더해진다.

예를 들면 0번째 행, 1번째 행은 중간에 있는 요소가 없기 때문에 안 겹치지만 2번째 행부터는 가장 첫 열인 8과 가장 끝 열인 0을 제외하고 중간에 있는 1은 그 전 행의 3과도 더해질 수 있고 8과도 더해질 수 있다.

지금 문제는 이 중에서 최댓값을 구하라고 했기 때문에 중복해서 더해지는 요소는 두 가지 경우 중 최댓값만 저장하면 된다.

이를 그림으로 표현하면 다음과 같다.

 

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const N = Number(input[0]);
input.shift();
input = input.map((element) => element.trim().split(" "));
const sum = Array.from(new Array(N), () => new Array());
sum[0].push(Number(input[0][0]));
if (N > 1) {
  for (let r = 1; r < N; r++) {
    for (let c = 0; c < input[r].length; c++) {
      if (c === 0) {
        sum[r].push(Number(sum[r - 1][c]) + Number(input[r][c]));
      } else if (c === r) {
        sum[r].push(Number(sum[r - 1][c - 1]) + Number(input[r][c]));
      } else {
        sum[r].push(
          Math.max(Number(sum[r - 1][c - 1]), Number(sum[r - 1][c])) +
            Number(input[r][c])
        );
      }
    }
  }
}
console.log(Math.max(...sum[N - 1]));