[백준-1932] 정수 삼각형 / Python

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

1932번: 정수 삼각형

n = int(input())
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))

k = 2
for i in range(1, n):
    for j in range(k):
        if j == 0:
            data[i][j] = data[i][j] + data[i - 1][j]
        elif i == j:
            data[i][j] = data[i][j] + data[i - 1][j - 1]
        else:
            data[i][j] = max(data[i - 1][j - 1], data[i - 1][j]) + data[i][j]
    k += 1

print(max(data[-1]))

 

해설

찾을 수 있는 패턴은 세 가지다.

진행 라인의 처음 값, 마지막 값, 나머지 값을 정하는 경우다.

라인의 처음 값은 현재 값 + 이전의 처음 값

라인의 마지막 값은 현재 값 + 라인의 마지막 값

그 외 나머지 값들은 마주하고 있는 양 쪽 대각선의 이전 값들 중 더 큰 값을 현재 값과 더해주면 된다.