[백준 1932번] 정수 삼각형 - 자바스크립트(nodejs)

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

1932번: 정수 삼각형

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

const dp = [input[0]];

for (let i = 1; i < input.length; i++) {
  let arr = [];
  for (let j = 0; j < input[i].length; j++) {
    let value;
    if (j === 0) {
      value = input[i][0] + dp[i - 1][0];
    } else if (j === input[i].length - 1) {
      value = input[i][j] + dp[i - 1][dp[i - 1].length - 1];
    } else {
      value = Math.max(input[i][j] + dp[i - 1][j - 1], input[i][j] + dp[i - 1][j]);
    }

    arr.push(value);
  }

  dp[i] = arr;
}

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

dp문제지만 타 문제와 다르게 한 칸씩 늘어날수록 길이가 1개씩 점점 증가한다!

이 처리를 해줘야 한다.

맨 왼쪽의 값은 무조건 위의 0번째 인덱스만 더할 수 있으며,

맨 오른쪽 값은 위의 마지막 인덱스만 더할 수 있다.

 

중간값들은 본인의 인덱스보다 1이 작거나, 본인의 인덱스만 더할 수 있다.

ex) 더할 수 있는 인덱스만 작성한 것

그러므로 양 끝 값 처리를 해주고 중간값들은 더한 값 중의 최댓값만 점점 저장해 가면 된다.

 

결과적으로 한 칸씩 늘어갈수록 최댓값으로 초기화해 끝까지 처리한 후 마지막 배열의 최댓값을 return 해주면 된다.