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

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 정수 삼각형

문제

제한사항

📌 내가 생각한 풀이

높이가 n번째인 배열은 자신의 오른쪽 위, 왼쪽 위 값중에 더 큰 값을 더해서 내려와야하므로, dp를 사용하여 문제를 해결하자

1. 높이가 n에 존재하는 배열이면 n-1번째 존재하는 배열에서 인덱스 i-1, i번째 값을 비교하여 더해주자
2. 인덱스가 0이거나 마지막 번호이면 무조건 n-1번째 배열에서 첫번째 || 마지막번째 값을 더해야한다.
3. 다 더한 값을 배열로 표현하여 최대값 출력!

function solution(triangle) {
  var answer = 0;
  triangle.forEach((data, height) => {
    if (height > 0) {
      let upVal = triangle[height - 1];
      let currentVal = data;
      for (var i = 0; i < currentVal.length; i++) {
        if (i === 0) {
          currentVal[0] += upVal[0];
        } else if (i === currentVal.length - 1) {
          currentVal[currentVal.length - 1] += upVal[upVal.length - 1];
        } else {
          let [forward, back] = [i - 1, i];
          if (upVal[forward] > upVal[back]) {
            currentVal[i] += upVal[forward];
          } else {
            currentVal[i] += upVal[back];
          }
        }
      }
    }
  });
  return Math.max(...triangle[triangle.length - 1]);
}

📌 느낀점

비교적 간단하게 풀리는 가장 기본적인 DP 문제였다.