[백준/파이썬] 1932번

📍백준 1932 문제

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

코드

import sys
input = sys.stdin.readline

n = int(input())

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

res = [tri[0]]

for i in range(1, n):
    temp = []
    for j in range(len(tri[i])):
        if j == 0:
            temp.append(tri[i][j]+res[-1][0])
        elif j == len(tri[i])-1:
            temp.append(tri[i][j]+res[-1][-1])
        else:
            temp.append(tri[i][j]+max(res[-1][j], res[-1][j-1]))
    res.append(temp)
print(max(res[-1]))

풀이

• 삼각형에서 맨 처음에 위치한 값과 마지막에 위치한 값은 비교 할 값이 없으므로 바로 위의 값을 더해주면 된다.
• 나머지 값은 자신의 현재 위치 [j]에서 이전 값인 [j-1]과 [j]번째 값 중 최대값을 찾아, 현재 값과 더하면 된다.
• 이 값들을 temp라는 배열에 더해준다.
• res(누적된 값) 라는 배열을 만들어서 temp를 추가한다.