[ 𝗽𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗲𝗿𝘀 ] 정수 삼각형 - DP | JavaScript

🎯 문제 설명

🧩 프로그래머스 Lv.3 - 정수 삼각형

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

🥅 제한 조건

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

📍 입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

👩🏻‍💻 문제 풀이

주어진 삼각형의 꼭대기부터 아래로 내려가면서 왼쪽 아래 또는 오른쪽 아래로만 이동합니다. 맨 아래쪽까지 내려갔을 때 얻을 수 있는 최댓값을 구하는 것입니다.

이 문제의 경우에는 Bottom-up 방식으로 계산하는 것이 효율적입니다. 이 경우에는 한 번씩만 계산하면서 값을 갱신하기 때문입니다.

Top-down 방식으로 풀려면 각 경로마다 재귀 함수가 호출되면서 여러 번 중복해서 계산하게 되고, 메모이제이션을 사용하려면 구현이 더 복잡해집니다.

DP를 사용해 Bottom-up으로 풀겠습니다. dp 배열은 주어진 삼각형을 복사해서 사용하겠습니다. 값을 갱신하는 식으로 구하면 추가 배열 없이 해결할 수 있습니다.

const dp = triangle.map(row => [...row]);

이 때 dp[i]는 다음과 같습니다.

dp[i][j] = triangle[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);

맨 아랫줄은 그대로 사용하고 아래에서 두 번째 줄부터 위로 올라오며 값을 갱신해 나값니다.

for(let i = dp.length - 2; i >= 0; i--){
	for(let j = 0; j < dp[i].length; j++){
		dp[i][j] += Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
	}
}

이렇게 하면 꼭대기에 최댓값이 저장됩니다.

return dp[0][0]

하지만, 제출하면 효율성 테스트 1번에서 시간초과가 납니다.

해당 코드에서 불필요하면서도 시간을 들이는 부분이 뭘까 하다가, triangle배열이 크다면 dp배열을 만들면서 map으로 복사하는 과정에서 시간이 많이 걸릴 수도 있다고 생각했습니다.

따라서 triangle배열 자체를 수정하는 방식으로 수정해보았고, 통과하였습니다. 아무래도 자바스크립트의 언어 특성상 map 연산은 내부적으로 비용이 크게 들고 상대적으로 다른 언어보다 느려서 그런 것 같습니다.

최종 코드

function solution(triangle) {
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
    }
  }
  return triangle[0][0];
}