[백준/python] 1932번 정수 삼각형

<문제>

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

1932번: 정수 삼각형

 

<풀이 - 코드>

 

<풀이 - 해설>

dp(동적 계획법 - Dynamic Programming)인 문제이다. 처음에 봤을 때는 그리디가 생각이 났지만, 현재 기준으로 높은 숫자가 아닌, 합 중 최대값을 출력해야되므로 dp를 이용하여 풀어야 된다.

양 끝에 있는 숫자들은 더할 수 있는 값들이 정해져있으므로, 제일 왼쪽과 제일 오른쪽의 숫자들은 이전 값들과 누적된 합들을 합해준다. 그리고 중간에 있는 값들은 dp 내에 있는 현재 idx와 이전 idx 값 중 비교하여 큰 값을 불러와서 출력하도록 한다.

그 부분이 "#나머지 숫자" 부분의 로직이다. max 함수를 이용했고, 하나의 행에서 같은 배열로 묶어서 누적된 값들을 추가해준다. 그래서 그 중 맨 마지막에 있는 배열 중 최대값을 출력하도록 한다.