[파이썬]백준 1932 정수삼각형

링크

백준 1932 트리순회

간만에 푼것치고 꽤나 깔끔하게 정답을 찾은 것 같다.
리스트를 트리라 가정한다.
메모에는 루트노드부터 해당 자식까지의 값을 누적합해나가며 같은 모양의 트리를 만든다.

양 끝 노드가 아닌 가운데에 속한 노드의 경우 부모가 2개가 되는데 이 경우 누적합이 큰 값을 취한다. (코드에서 if tmp: 부분)

가장 마지막 레벨까지 내려간 후 마지막 레벨의 max를 취한다.

정답 코드

import sys; input = sys.stdin.readline

N = int(input())
tree = []
memo = []
for _ in range(N):
    tree.append(list(map(int, input().split())))

memo.append(tree[0])
for i in range(1, N):
    tmp = []
    for j in range(1, i + 1):
        if tmp:
            tmp[-1] = max(tmp[-1], memo[i - 1][j - 1] + tree[i][j - 1])
        else:
            tmp.append(memo[i - 1][j - 1] + tree[i][j - 1])
        tmp.append(memo[i - 1][j - 1] + tree[i][j])
    memo.append(tmp)

print(max((memo[-1])))

알게된 것👨‍💻

• dp에 취한다