삼각 점수판 최대 경로 점수
자바스크립트 코딩테스트 문제로 triangle-dp 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
숫자 삼각형에서 위에서 아래로 내려가며 얻을 수 있는 최대 점수를 구하는 문제입니다.
문제 설명
정수로 이루어진 삼각형 배열 triangle이 주어집니다.
맨 위 칸에서 시작해서 맨 아래 줄까지 내려가려고 합니다. 현재 줄의 i번째 칸에 있다면, 다음 줄에서는 아래쪽의 두 칸 중 하나로만 이동할 수 있습니다.
- 같은 인덱스
i - 바로 오른쪽 인덱스
i + 1
지나간 칸들의 점수 합이 가장 크게 되도록 이동했을 때, 그 최대 점수를 반환하는 maxTriangleScorePath 함수를 작성하세요.
제한사항
triangle의 길이는1이상200이하입니다.triangle[i]의 길이는 항상i + 1입니다.- 각 원소는
-1,000이상1,000이하의 정수입니다. - 반드시 맨 위에서 시작해 맨 아래 줄까지 내려가야 합니다.
예시
- 입력:
triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]→ 출력:30 - 입력:
triangle = [[-1], [2, 3], [1, -5, 1]]→ 출력:3 - 입력:
triangle = [[5], [-2, -3], [4, 9, 1], [-8, 1, 2, 3]]→ 출력:12
힌트
- 각 칸에 도착하는 최대 점수만 알면, 그 아래 칸의 최대 점수도 계산할 수 있습니다.
- 현재 칸으로 올 수 있는 부모는 많아야 2개뿐입니다.
- 양 끝 칸은 부모가 1개뿐이라는 점을 먼저 정리하면 구현이 깔끔해집니다.
해설
이 문제는 완전탐색으로 모든 경로를 다 시도하면 경우의 수가 빠르게 커집니다.
대신 각 칸까지 도달했을 때의 최대 누적 점수를 저장하면 됩니다.
예를 들어 dp[row][col]을 row번째 줄 col번째 칸에 도착했을 때 얻을 수 있는 최대 점수라고 두면,
- 맨 왼쪽 칸은 왼쪽 위 부모가 없으므로 바로 위 칸에서만 올 수 있고
- 맨 오른쪽 칸은 오른쪽 위 부모가 없으므로 왼쪽 위 칸에서만 올 수 있으며
- 중간 칸은
왼쪽 위,바로 위중 더 큰 누적값을 선택하면 됩니다.
점화식은 다음과 같습니다.
leftParent = col > 0 ? dp[row - 1][col - 1] : -Infinity;
rightParent = col < row ? dp[row - 1][col] : -Infinity;
dp[row][col] = triangle[row][col] + Math.max(leftParent, rightParent);
마지막 줄까지 계산한 뒤, 마지막 줄의 최댓값이 정답입니다.
이 방식은 각 칸을 한 번씩만 계산하므로 시간 복잡도는 O(n^2)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.