백준1932(파이썬) - 정수 삼각형

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

1932번: 정수 삼각형

• 이 문제는 보자마자 DP 임을 알고 하나하나 그려보았다.
• 처음에는 메모이제이션을 떠올리긴 했지만 사용하지 않고 n만큼 for문을 돌리면서 dp[i] 에 생길 수 있는 숫자를 다 넣어서 그 중에서 최댓값을 출력하려고 생각했으나 내가 짰던 코드로는 전체 경우의 수를 다 담을 수 없었다.
• 그래서 아래에서 부터 위로 생각하였고, 그 과정에서 max를 통해서 값을 갱신하면서 답을 구할 수 있었다.
• 아래에서 부터 위로 생각했을 때, 양쪽 끝은 각 숫자의 위에 있는 수를 받아오고 양쪽 끝을 제외한 나머지 숫자들은 왼쪽 위, 오른쪽 위에서 큰 수를 더해나가면 되는 방식으로 구현하였다.

import sys
input = sys.stdin.readline

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

for i in range(1,n):
    for j in range(i+1):
        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]
            
print(max(data[-1]))