문제
숫자 삼각형은 0행에 값이 하나, 1행에 두 개, 이런 식으로 이루어져 있습니다. 꼭대기에서 출발해 한 번에 한 행씩 내려가는데, 매번 바로 아래 값이나 그 오른쪽 아래 값으로만 이동할 수 있습니다(위치 i에서 i 또는 i + 1로). 지나간 값의 합이 가장 큰 경로를 찾으세요. 모든 경로를 시도하면 행마다 작업량이 두 배가 되지만, 맨 아래 행부터 위로 올라가며 계산하면 이차 시간으로 줄어듭니다.
triangle_max_path_sum(triangle) 함수를 구현하세요.
입력
triangle: 위에서 아래 순서의 행들입니다. r행에는 값이 r + 1개 있으며 음수일 수도 있습니다.
출력
꼭대기에서 맨 아래까지 가는 경로의 합 중 가능한 가장 큰 값을 반환합니다. 빈 삼각형이면 0을 반환합니다.
제약 조건
0 ≤ rows ≤ 100; −1000 ≤ value ≤ 1000
예시
입력:
triangle = [
[4],
[7, 2],
[1, 9, 5],
[6, 3, 8, 2]
]
예상 출력:
expected = 28
입력:
std::vector<std::vector<long long>> triangle = {
{4},
{7, 2},
{1, 9, 5},
{6, 3, 8, 2}
};
예상 출력:
long long expected = 28;
입력:
long[][] triangle = new long[][] {
new long[] {4},
new long[] {7, 2},
new long[] {1, 9, 5},
new long[] {6, 3, 8, 2}
};
예상 출력:
long expected = 28;
설명
가장 좋은 경로는 4, 7, 9, 8(위치 0, 0, 1, 2)이고 합은 28입니다.
입력:
triangle = [
[-3],
[5, -8],
[-1, 2, 9]
]
예상 출력:
expected = 4
입력:
std::vector<std::vector<long long>> triangle = {
{-3},
{5, -8},
{-1, 2, 9}
};
예상 출력:
long long expected = 4;
입력:
long[][] triangle = new long[][] {
new long[] {-3},
new long[] {5, -8},
new long[] {-1, 2, 9}
};
예상 출력:
long expected = 4;
설명
음수가 있을 때 −3, 5, 2는 4, −3, −8, 9는 −2이므로 답은 4입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
맨 아래 행부터 시작하세요. 맨 아래 칸에서 출발하는 최선의 경로는 그 칸의 값 자체입니다.
힌트 2
어떤 칸에서의 최선의 경로는 그 칸의 값에 바로 아래 두 칸의 최선 값 중 큰 쪽을 더한 것입니다.
힌트 3
모든 행을 위로 올라가며 처리하고 나면 꼭대기 칸에 답이 들어 있습니다.
예상 복잡도
시간 O(rows²), 추가 공간 O(rows)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.