[동적계획법] 프로그래머스 L3 '정수 삼각형' (Python)

<문제 링크>

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

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

1932번: 정수 삼각형

---

<문제 풀이>

1. 삼각형의 꼭대기에서 바닥까지의 합을 구하는 것이므로, 아래 칸으로 이동할 때 윗 칸의 숫자를 더해준다.
2. 삼각형의 왼쪽 변의 숫자는 항상 왼쪽 숫자를 더하고, 오른쪽 변의 숫자는 항상 오른쪽 숫자를 더한다. 
3. 삼각형의 가운데 숫자들은 자신의 위의 숫자 2개에서 큰 값을 더하면 된다. 
4. 숫자를 다 더한 바닥의 숫자들 중 최댓값을 반환한다.

<코드>

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