프로그래머스 Level3 "정수 삼각형"

문제

프로그래머스 Level3 정수 삼각형

---

풀이

삼각형의 최상단부터 내려오면서 계산을 해야한다.

각 층마다 좌측과 우측은 바로 위 숫자 하나와 계산을 하면 되니 각각triangle[i-1][j] triangle[i-1][j-1]과 계산을 하면 되고,
중간에 있는 숫자는 위 두개의 숫자중 값이 더 큰 값과 계산을 하면된다.

`i=1` 일 때, 중간에 있는 값이 없으니 3과 8이 7과 더해진다. `i=2` 일 때, 좌측의 8과 우측의 0은 10과 15랑 각각 계산이되며, 중간에 있는 1은 10과 15중 큰 값인 15과 계산을 한다. 이런 식으로 계산을 반복하면 위 그림과 같다. 마지막 줄에서 가장 큰 값인 30이 정답이 된다.

---

Python 코드

def solution(triangle):
  for i in range(1, len(triangle)):
    for j in range(len(triangle[i])):
      if j == 0:
        triangle[i][j] += triangle[i-1][j]
      elif i == j:
        triangle[i][j] += triangle[i-1][j-1]
      else:
        triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])
  answer = max(triangle[-1])
  return answer