[백준 1932] 정수 삼각형 with Node.js

문제 링크

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

1932번: 정수 삼각형

풀이

const solve = (n, triangle) => {
  if (n === 1) return triangle[0][0];
  else if (n === 2) return triangle[0][0] + Math.max(...triangle[1]);
  for (let i=n-2; i>=0; i--) {
    triangle[i].forEach((v, idx, arr) => {
      arr[idx] = v + Math.max(triangle[i+1][idx], triangle[i+1][idx+1]);
    });
  }
  return triangle[0][0];
};

const [n, ...triangle] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
triangle.forEach((v, i, arr) => arr[i] = v.split(' ').map(vv => +vv));
console.log(solve(+n, triangle));

n이 1 일 때는 입력된 수 하나를, n이 2 일 때는 밑에 줄 두  수 중 최댓값과 맨 위 수를 더한 값을 출력한다.

n이 3 이상일 때는 n-1번째 줄부터 바로 아랫줄에 연결된 두 수 중 최댓값을 더한다.

 

예를 들어, 예시에서 제시된 삼각형에서 4번째 줄인 2 7 4 4를

각 숫자에 연결된 바로 아랫줄 두 수 중 최댓값과 더하여 7 12 10 10으로 만든다.

이런식으로 맨 윗줄까지 거치면 최종적으로 삼각형의 맨 위에 합의 최댓값이 저장된다.