백준 1932 정수 삼각형

문제

오랜만에 dp 문제 보니까 막 반갑고 재밌고.. 정수 삼각형에서 대각선 왼/오로 가면서 각 나올 수 있는 최댓값을 계속 누적해서 메모이제이션 하면서 마지막 줄의 최댓값을 가져오면 되는 문제이다.

처음에는 이 삼각형을 전부 n*(2n-1)의 배열에 넣으려고 했다. 그래야 탐색이 쉬워질 것 같았다. 근데 어떻게 할 지 제대로 생각이 안 났다..별찍기조차 제대로 안해본 나.. 여기서부터 막히다보니 굳이 이렇게 풀어야하나?라는 생각이 들었고, 기존의 삼각형 입력을 배열로 바꾸어 그대로 사용할 수 있지 않을까 싶었다.

가만 보면 삼각형이 밑으로 내려가면서 최댓값을 구하는 방식은 간단하다. 왼쪽 대각선이나 오른쪽 대각선의 위치를 보고 있는 누적값들 중에 최댓값을 골라 기존의 값에 더하기만 하면 된다.

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

그렇다면 이와 같은 배열을 받았다고 한다면, 양 끝을 제외한 오른쪽 대각선 위의 수는 이전 배열에서 인덱스의 위치는 그대로 있는 쪽이고, 왼쪽 대각선 위의 수는 이전 배열에서 현재 위치 인덱스의 -1 위치에 있다.

그러므로 그냥 이걸 그대로 받아 계산하면 되는데, 문제는 양끝단이다. 왼쪽 끝은 오른쪽 대각선 수만, 오른쪽 끝은 왼쪽 대각선 수만 있기 때문이다. 그냥 분기처리 해주면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [N, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const n = +N;
const dpArr = rest.map((r) => r.split(" ").map(Number));
 
for (let i = 1; i < n; i++) {
  for (let j = 0; j < dpArr[i].length; j++) {
    if (j === 0) {
      dpArr[i][j] += dpArr[i - 1][j];
      continue;
    } else if (j === dpArr[i].length - 1) {
      dpArr[i][j] += dpArr[i - 1][j - 1];
      continue;
    } else {
      dpArr[i][j] += Math.max(dpArr[i - 1][j], dpArr[i - 1][j - 1]);
    }
  }
}
console.log(Math.max(...dpArr.at(-1)));
 

오랜만에 빠르게 한번에 풀어서 기분이 매우 좋군.