[백준] 1932번 정수삼각형 - JavaScript(NodeJS)

문제

1932번: 정수 삼각형

 

풀이

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

다음 삼각형에서 꼭대기에서 아래로 내려오면서, 대각선으로 이동한다.

 

선택한 수의 합이 최대일 때를 구하면 된다.

삼각형의 크기 N은 (1 <= N <= 500)의 범위를 가진다.

 

dp라는 배열을 기준으로 생각해서, dp[0]을 맨 위층, dp[1]을 그 다음층(위에서 두번째 층) ... 이라고 생각한다.

각 층 dp[i]마다 배열을 가지는데, 그 배열의 인덱스는 그 층의 특정 인덱스에 도달하기까지 선택한 수의 합의 최대값이다.

즉, dp[1][1]의 값은 위에서 두번째 층인 8에 도달할 때 까지 선택한 수의 최대값인 7+8=15를 가진다.

 

N=1일 때, dp[0] = [7] 이다.
N=2일 때, dp[1] = [7+3, 7+8] 이다.
N=3일 때, dp[2] = [7+3+8, Min(7+3+1, 7+8+1), 7+8+0] 이다.

 

 

일반화해보면,

 

dp[N-1][0]의 값은 0->0->0->0 인덱스를 거쳐가므로 1개의 경우의 수만 존재한다.
dp[N-1][N-1]의 값은 0->1->2->3...의 각 행의 마지막 인덱스를 거쳐가므로 1개의 경우의 수만 존재한다.
dp[N-1][K]의 값은 K를 도착한 모든 경우의 수 중 가장 큰 값을 구하면 된다.

 

K 인덱스 위치에 도착할 수 있는 방법은
이전 층(N-2 층)의 K-1 인덱스에서 오거나, K 인덱스에서 오는 방법 2가지이다.

 

 

이 두개의 숫자중에 큰 숫자를

이를 코드로 나타내본다.

 

코드

const sol = ([n, ...arr]) => {
  n = +n;
  const dp = [];
  for (let i = 0; i < n; i++) {
    dp.push(arr[i].split(" ").map((v) => +v));
  }

  for (let i = 1; i < n; i++) {
    for (let j = 0; j <= i; j++) {
      let prev;
      if (j === 0) prev = dp[i - 1][j];
      else if (j === i) prev = dp[i - 1][j - 1];
      else prev = Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
      dp[i][j] += prev;
    }
  }
  console.log(Math.max(...dp[n - 1]));
};

const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    sol(input);
    process.exit();
  });