[JavaScript/DP] 백준 실버 1 : 1932 - 정수 삼각형

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

1932번: 정수 삼각형

---

📌 작성한 코드

//1932
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input.shift());
const board = input.map((i) => i.split(" ").map(Number));

const dp = Array.from({ length: N }, () => new Array(N).fill(0));
dp[0][0] = board[0][0];

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

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

📌 설명 

- 정의 : dp[i][j] = i층에서 j번째 숫자까지 도달하는데 선택된 숫자들의 최댓값

- 점화식 :  `dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + board[i][j]`

- 왼쪽 대각선 위의 좌표는 [i-1][j-1]이고, 오른쪽 대각선 위의 좌표는 [i-1][j]이다. 

for (let i = 1; i < N; i++) {
    for (let j = 0; j < i + 1; j++) {
        if (j - 1 < 0) { // 왼쪽 대각선이 존재하지 않으면 무조건 오른쪽 대각선에서 내려와야 함
            dp[i][j] = dp[i - 1][j] + board[i][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + board[i][j];
        }
    }
}

✅ 성공