모든 챌린지
보통 0명 해결 정답률 0%

삼각형의 최대 경로 합

숫자 삼각형의 꼭대기에서 맨 아래 행까지 가는 경로의 합 중 가장 큰 값을 구합니다.

배우게 될 내용

  • 지수 시간 탐색을 동적 계획법으로 바꿀 수 있다
  • 아래 행의 결과를 합칠 수 있다
  • 음수 값과 빈 입력을 처리할 수 있다

문제

원문 보기 (영어)

숫자 삼각형은 0행에 값이 하나, 1행에 두 개, 이런 식으로 이루어져 있습니다. 꼭대기에서 출발해 한 번에 한 행씩 내려가는데, 매번 바로 아래 값이나 그 오른쪽 아래 값으로만 이동할 수 있습니다(위치 i에서 i 또는 i + 1로). 지나간 값의 합이 가장 큰 경로를 찾으세요. 모든 경로를 시도하면 행마다 작업량이 두 배가 되지만, 맨 아래 행부터 위로 올라가며 계산하면 이차 시간으로 줄어듭니다.

triangle_max_path_sum(triangle) 함수를 구현하세요.

입력

triangle: 위에서 아래 순서의 행들입니다. r행에는 값이 r + 1개 있으며 음수일 수도 있습니다.

출력

꼭대기에서 맨 아래까지 가는 경로의 합 중 가능한 가장 큰 값을 반환합니다. 빈 삼각형이면 0을 반환합니다.

제약 조건

0 ≤ rows ≤ 100; −1000 ≤ value ≤ 1000

예시

예시 1
입력:
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입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.