[백준] JS 1932번 정수 삼각형

문제

정수 삼각형
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

풀이

최초에 생각해낸 풀이는 첫 행의 j열과 다음 행의 j열, j+1열과의 합이 더 큰쪽을 선택하여 할당하도록 하였으나, 연산이 중복되는 열이 있어, 그 결과가 큰 차이가 있었다.

따라서, 어떻게 하면 중복된 계산을 피할까 고민하였다.

중복된 연산을 피하려면 애초에 특정 원소에 한 번만 접근하면 된다는 결론에 따라, 2행(인덱스 1)부터 이전 행의 같은 열의 원소와 -1열의 원소 중 더 큰 수와 더하여 그 값을 할당하는 식으로 전개하였다.

각 행의 1열과 마지막 열은 위와 같은 방식으로 계산했을 때 out of range가 되기 때문에 1열은 1열끼리만 계산하도록 하고, 각 행 마지막 열도 마찬가지로 연산하도록 조건문을 작성하였다.

코드

const input = require("fs")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n");

let n = +input.shift();

let dp = input.map((x) => x.split(" ").map((e) => +e));
// console.log(n, dp);
for (let i = 1; i < n; i++) {
  for (let j = 0; j < dp[i].length; j++) {
    if (j == 0) dp[i][j] += dp[i - 1][j];
    else if (j == dp[i].length - 1) dp[i][j] += dp[i - 1][j - 1];
    else dp[i][j] += Math.max(dp[i - 1][j], dp[i - 1][j - 1]);
  }
}

console.log(Math.max(...dp[n - 1]));