코딩 테스트 및 알고리즘/이것이 취업을 위한 코딩테스트다
Q32. 정수 삼각형
띠리링구
2022. 4. 12. 23:48
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
삼각형을 위에서 아래로 쫙 훑으면서 각 숫자가 아래층 대각선 숫자에 더해졌을 때의 최대값을 계속 갱신해주면된다.
n = int(input())
tri = []
dp = []
for _ in range(n):
line = list(map(int,input().split()))
tri.append(line)
dp.append(line[:])
for i in range(n-1):
for j in range(len(tri[i])):
dp[i+1][j] = max(dp[i+1][j], tri[i+1][j] + dp[i][j])
dp[i+1][j+1] = max(dp[i+1][j+1], tri[i+1][j+1] + dp[i][j])
print(max(dp[n-1]))