정수 삼각형

문제

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제입니다.

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동할 수 있습니다.
예를 들어 어떤 칸에서 아래층으로 이동할 때는 바로 아래에 연결된 두 칸 중 하나로만 이동할 수 있습니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 반환해야 합니다.

제한사항

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

입출력 예

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

사용 알고리즘

이 문제는 동적 계획법, 즉 DP를 사용해 해결할 수 있습니다.

꼭대기에서 아래로 내려가며 모든 경로를 탐색하면 가능한 경로가 매우 많아집니다.
삼각형의 높이가 최대 500이므로 완전 탐색으로는 효율적으로 해결하기 어렵습니다.

대신 아래층부터 위층으로 올라가면서, 각 칸에서 선택할 수 있는 최댓값을 누적합니다.

예를 들어 어떤 칸에서 아래층으로 이동할 수 있는 칸이 두 개라면, 그 둘 중 더 큰 값을 현재 칸에 더합니다.

triangle[floor - 1][i] += max(triangle[floor][i], triangle[floor][i + 1])

이 과정을 바닥층부터 꼭대기까지 반복하면, 최종적으로 triangle[0][0]에는 꼭대기에서 바닥까지 이동했을 때 얻을 수 있는 최댓값이 저장됩니다.

풀이 과정

1. 가장 아래층의 인덱스를 floor에 저장합니다.
2. 아래층부터 위층으로 한 층씩 올라갑니다.
3. 현재 층의 인접한 두 값을 비교합니다.
4. 둘 중 큰 값을 바로 위층의 해당 칸에 더합니다.
5. 이 과정을 꼭대기까지 반복합니다.
6. 마지막에 triangle[0][0]을 반환합니다.

Python 풀이

# 아래에서 위로 올라가기
def solution(triangle):

    floor = len(triangle) - 1  # N층의 인덱스

    while floor > 0:  # N, N-1, ..., 2, 1
        for i in range(floor):  # N번째 인덱스엔 0~N -> N+1개의 숫자가 있음
            # 바로 위층의 칸에 아래칸의 두 개 중 큰 값을 더해줌
            triangle[floor - 1][i] += max(triangle[floor][i], triangle[floor][i + 1])

        floor -= 1  # 층 하나 올라가기

    return triangle[0][0]

코드 설명

floor = len(triangle) - 1

triangle의 마지막 인덱스를 구합니다.
이 값은 가장 아래층의 인덱스를 의미합니다.

while floor > 0:

가장 아래층부터 시작해서 꼭대기층까지 올라갑니다.
floor가 0이 되면 꼭대기까지 계산이 끝난 상태입니다.

for i in range(floor):

현재 층의 바로 위층에 있는 값들을 갱신합니다.
floor번째 층에는 floor + 1개의 숫자가 있고, 그 위층에는 floor개의 숫자가 있습니다.

triangle[floor - 1][i] += max(triangle[floor][i], triangle[floor][i + 1])

바로 위층의 i번째 칸은 아래층의 i번째 칸 또는 i + 1번째 칸으로 이동할 수 있습니다.
따라서 두 값 중 더 큰 값을 위층의 값에 더합니다.

return triangle[0][0]

모든 계산이 끝나면 꼭대기 값에 최대 경로 합이 저장됩니다.

시간복잡도

삼각형의 높이를 N이라고 하겠습니다.

삼각형의 모든 칸을 한 번씩 확인하며 값을 갱신합니다.
삼각형에 들어 있는 전체 숫자의 개수는 다음과 같습니다.

1 + 2 + 3 + ... + N = N(N + 1) / 2

따라서 시간복잡도는 다음과 같습니다.

O(N^2)

공간복잡도

별도의 DP 배열을 만들지 않고, 주어진 triangle 배열을 직접 갱신합니다.

따라서 추가로 사용하는 공간은 상수 공간입니다.

O(1)

단, 입력 배열을 직접 수정하지 않는 방식으로 풀 경우에는 별도의 DP 배열이 필요할 수 있습니다.

핵심 정리

• 최대 경로 합을 구하는 문제이므로 DP를 사용한다.
• 아래층부터 위층으로 올라가며 선택 가능한 두 값 중 큰 값을 누적한다.
• 최종적으로 triangle[0][0]에 전체 경로의 최댓값이 저장된다.
• 입력 배열을 직접 갱신하면 추가 공간을 거의 사용하지 않고 해결할 수 있다.