[실버 1] 백준 1932 - 정수 삼각형 (파이썬)

https://www.acmicpc.net/problem/1932

풀이

정수로 이루어진 삼각형이 주어질 떄, 맨 위에서부터 아래로 내려가면서 선택한 수의 합이 최대가 되도록 경로를 찾는 문제이다.

한 칸 아래로 이동할 떄는 바로 아래 또는 바로 아래 오른쪽으로만 이동할 수 있다.

N = int(input())  # 삼각형의 높이
A = [list(map(int, input().split())) for _ in range(N)]  # 삼각형 데이터

A는 삼각형 형태의 숫자 배열이다.

D = [[0] * (i + 1) for i in range(N)]
D[0][0] = A[0][0]

D[i][j]는 i번째 줄, j번째 위치까지 올 때 최대 합을 저장하는 DP테이블이다.

첫번째 숫자는 그대로 초기화한다.

for i in range(1, N):
    for j in range(i + 1):
        left, right = 0, 0
        if j > 0:
            left = A[i][j] + D[i - 1][j - 1]  # 왼쪽 위에서 내려오는 경우
        if j < i:
            right = A[i][j] + D[i - 1][j]      # 바로 위에서 내려오는 경우

        D[i][j] = max(left, right)

현재 위치 (i, j)는 두가지 방향에서 올 수 있다.

1. 왼쪽 위 : D[i - 1][j - 1]
2. 오른쪽 위 : D[i - 1][j]

가능한 방향에서 내려온 값 중 더 큰 값에 현재 값을 더해 갱신한다.

시간 복잡도 분석

• O(N ^ 2)
• 이중 반복문이므로, N이 최대 500일때도 충분히 해결 가능하다.

코드

# 백준 1932 - 정수 삼각형
# 분류 : 다이나믹 프로그래밍

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

D = [[0] * (i + 1) for i in range(N)]
D[0][0] = A[0][0]

for i in range(1, N) :
    for j in range(i + 1) :
        left, right = 0, 0
        if j > 0 :
            left = A[i][j] + D[i - 1][j - 1]
        if j < i :
            right  = A[i][j] + D[i - 1][j]

        D[i][j] = max(left, right)

print(max(D[N - 1]))