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

🔴 문제

정수 삼각형

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, ...inputs] = fs.readFileSync(path).toString().split('\r\n');
const triangle = inputs.map((it) => it.split(' ').map((it) => Number(it)));

for (let i = 1; i < Number(n); i++) {
  for (let j = 0; j < triangle[i].length; j++) {
    if (j === 0) {
      triangle[i][j] += triangle[i - 1][0];
      continue;
    } else if (j === triangle[i].length - 1) {
      triangle[i][j] += triangle[i - 1][j - 1];
      continue;
    } else {
      triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
    }
  }
}

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

🟢 풀이

⏰ 소요한 시간 : -

한 10분간 풀이하다가 이건 내가 못푼다 판단하고 바로 답을 봤다.
DP 유형이라는 것은 알았지만 공식을 적용하기 어려웠다. ㅠ
이 문제는 어떤 위치의 값은 자기보다 위에 있는 두 가지 값으로부터 올 수 밖에 없다는 점을 이용하여 기존 삼각형을 업데이트 시켜주는 것이다.
문제에서 주어진 테스트 케이스로 예를 들어보면 첫줄의 7부터 시작이니 그 다음 요소인 3과 8을 새로운 삼각형으로 업데이트 시켜주는데, 이 때 3을 만들수 있는 7과 값을 합쳐 업데이트 해준다. 8도 동일한 방법으로 업데이트 시켜주면 삼각형은 아래처럼 변화한다.

  7			       7
3   8     ->    10   15

지금은 3과 8에 관여할 수 있는 값이 7뿐이지만 3번째 줄 에 있는 1은 3과 8 두개의 값으로 부터 변화가 가능하다. 이때 우린 3과 8을 각각 10과 15로 변경해 줬으므로
1+10 과 1+15 중 더 큰 값으로 삼각형을 업데이트 시켜준다.
줄글로 풀이하려니 조금 어수선 한 것 같은데 아래의 ref 링크에서 자세히 확인할 수 있다.

🔵 Ref

https://stujune-to-devjune.tistory.com/60