[프로그래머스] 정수 삼각형 - JavaScript

최은우·2023년 7월 26일
0

Algorithms

목록 보기
7/14
function solution(triangle) {
  for (let i = 1; i < triangle.length; i++) {
    let n = triangle[i].length
    for (let j = 0; j < n; j++) {
      if (j === 0) {
        triangle[i][j] += triangle[i - 1][j];
      } else if (j === n - 1) {
        triangle[i][j] += triangle[i - 1][j - 1];
      } else {
        triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
      }
    }
  }

  return Math.max(...triangle[triangle.length - 1]);
}

풀이 방향

  • 동적 계획법을 사용하여 실행 시간을 줄여야합니다.
  • 위에서 부터 아래로 내려가며 최댓값만을 저장하며 진행합니다.

주의할 점

for문과 if문의 조건절에 있는 n들을 n으로 미리 계산하지 않고 triangle[i].length로 하면 그때 그때 계산해야 해서 시간이 더 걸리게 됩니다.


0개의 댓글