← 19주차 · DP 입문 (1차원)
보통DP

정수 삼각형

숫자로 이루어진 삼각형이 배열 triangle로 주어져요. triangle[0]은 원소 1개, 그다음 줄마다 원소가 하나씩 늘어나요. 맨 위에서 시작해 아래로 내려가는데, 한 칸 내려갈 때는 바로 아래 칸 또는 그 오른쪽 칸으로만 갈 수 있어요.

바닥에 닿을 때까지 지나온 수의 합이 가장 클 때 그 값을 반환해요.

위에서부터 내려가며 생각하면 경우가 갈라지지만, 아래에서 위로 올려 생각하면 쉬워져요. 바닥 바로 윗줄의 각 칸은 '자기 값 + 아래 두 칸 중 큰 값'으로 정해지고, 이걸 꼭대기까지 접어 올리면 꼭대기 한 칸이 답이에요.

예시

예시 1
입력
triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
출력
21
설명
2 → 4 → 7 → 8, 합이 21이에요.
예시 2
입력
triangle = [[5]]
출력
5

제한 사항

  • 1 ≤ triangle.length ≤ 500
  • triangle[r]의 길이는 r + 1이에요.
  • -10,000 ≤ 각 값 ≤ 10,000
맨 아랫줄을 복사해 dp로 시작해요. 아래에서 두 번째 줄부터 위로 올라가며, 각 칸을 triangle[r][c] + Math.max(dp[c], dp[c+1])로 갱신해요. 꼭대기까지 오면 dp[0]이 답이에요.
javascript
function triangleMaxPath(triangle) {
  const dp = [...triangle[triangle.length - 1]];
  for (let r = triangle.length - 2; r >= 0; r--) {
    for (let c = 0; c < triangle[r].length; c++) {
      dp[c] = triangle[r][c] + Math.max(dp[c], dp[c + 1]);
    }
  }
  return dp[0];
}
이전 문제도둑질
다음 문제최장 증가 부분 수열
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.