백준 1932. 정수 삼각형

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

1932번: 정수 삼각형

합이 최대가 되도록 삼각형의 구성요소를 한 행당 하나씩 뽑아 구성하면 된다. 다만 이 때, 아래층에 있는 수는 왼쪽 혹은 오른쪽 위 대각선에 있는 요소만 선택할 수 있다.

 

단순히 위에서부터 내려오면서 합을 누적시켜 구할 수 있는데, 이 때 양쪽 끝 요소의 경우 오른쪽 대각선 혹은 왼쪽 대각선 요소가 당연히 선택되므로 이에 따른 처리를 해주고, 중간에 낀 요소들은 좌우 대각선 요소를 비교해서 더 큰 값을 넣어주면 된다.

그 후 마지막 행에서 가장 큰 요소를 찾아주면 된다.

 

n = int(input())
tri = []
for _ in range(n):
    tri.append(list(map(int, input().split())))
k = 2
for i in range(1, n):
    for j in range(k):
        if j==0:
            tri[i][j] += tri[i-1][j]
        elif i==j:
            tri[i][j] += tri[i-1][j-1]
        else:
            tri[i][j] += max(tri[i-1][j], tri[i-1][j-1])
    k += 1
print(max(tri[n-1]))