처음에 이 문제를 접했을 때에는 단순히 이전 행에서 고를 수 있는 값 중 최대를 고르면 될 줄 알았다
그러나 문제 예시를 보면 알 수 있듯이 그 전 행의 값만 중요한게 아니라 전체적으로 최대합이 나올 수 있도록 하는게 중요한 문제이다.
그렇기때문에 더더욱 dp 를 사용해서 이 문제를 풀어야겠다고 느꼈다.
n = int(input())
triangle = [list(map(int,input().split())) for _ in range(n)]
for i in range(1,n):
for j in range(len(triangle[i])):
if j == 0:
triangle[i][j] += triangle[i-1][j]
elif j == len(triangle[i])-1:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += max(triangle[i-1][j],triangle[i-1][j-1])
print(max(triangle[n-1]))정수삼각형을 배열화 했을 때의 구조를 생각하면 세가지의 케이스가 있다
열의 인덱스가 0 일때 마지막일때 그리고 그외 이렇게 세가지이다.
이 부분을 고려하여 3개의 if문으로 케이스를 분류해주어 해결해주었다.
그리고 이전 행에서 고를 수있는 값중 max 인 값을 계속해서 배열에 더해서 저장하는 dp 알고리즘을 통해 문제를 해결해 주었다.
