[Level 3] 정수 삼각형

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

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

---

접근

위에서 아래로 내려올 때 최댓값을 더해가면서 내려온다. 최종적으로 마지막 행에서 정수 삼각형의 최댓값을 찾도록한다.

 

구현

위에서 아래로 내려올 때 인덱스 0은 이전 행의 0과 더해준다.

그리고 마지막 열은 이전 행의 마지막 열과 더해준다.

위 두 개의 경우를 제외하고 가운데 있는 수들은 이전 행의 왼쪽 열과 이전 행의 열 중 최댓값을 더하도록 한다.

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