[백준] 1932 정수 삼각형 node.js

문제 링크

1932번: 정수 삼각형

 

문제 유형

다이나믹 프로그래밍

 

문제 풀이

• 반복문을 통해 (N - 2)층부터 0층까지 차례로 정수들을 방문한다.
• 현재 위치의 값 = (바로 아래층의 연결된 값중 최댓값) + (현재 위치의 값)
• 0층에 저장된 최대 경로에 있는 수의 합을 출력한다.

 

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().split("\n");
const N = Number(input.shift());
const triangle = input.map((v) => v.split(" ").map((v) => +v));
console.log(solution(N, triangle));

function solution(n, triangle) {
  if (n === 1) return triangle[0][0];
  else if (n === 2) return triangle[0][0] + Math.max(...triangle[1]);
  for (let i = n - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
    }
  }
  return triangle[0][0];
}