[백준] 1932번 문제 (정수 삼각형) 파이썬(Python) 풀이

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

1932번: 정수 삼각형

t = int(input())
nums = [list(map(int, input().split())) for _ in range(t)]
dp = []

for n in nums:
    dp.append([0] * len(n))

dp[0][0] = nums[0][0]

for i in range(1, t):
    for j in range(len(nums[i])):
        if j == 0:
            dp[i][j] = max(dp[i][j], nums[i][j] + dp[i - 1][j])
        elif j == len(nums[i]) - 1:
            dp[i][j] = max(dp[i][j], nums[i][j] + dp[i - 1][j - 1])
        else:
            dp[i][j] = max(dp[i][j], nums[i][j] + dp[i - 1][j], nums[i][j] + dp[i - 1][j - 1])

print(max(dp[t - 1]))

dp 문제이다.

삼각형의 꼭대기부터 아래로 내려오며, 최대값을 반복적으로 구하며 저장한다.

그리고 삼각형의 마지막 줄 dp[t - 1] 중에 제일 큰 값을 출력한다.