[프로그래머스-Lv3] 정수 삼각형 / Python

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

import sys

input = sys.stdin.readline

triangle = [list(map(int, input().split())) for _ in range(int(input()))]


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] + triangle[i][j]
            elif j == len(triangle[i]) - 1:
                triangle[i][j] = triangle[i - 1][-1] + triangle[i][j]
            else:
                triangle[i][j] = (
                    max(triangle[i - 1][j - 1], triangle[i - 1][j]) + triangle[i][j]
                )
    return max(triangle[-1])


print(solution(triangle))

 

해설

왼쪽 대각선 위, 오른쪽 대각선 위 중 더 큰 값을 현재 값에 더한다.

여기서 생각해야할 조건은 라인의 첫 번째 값과 마지막 값이다. 이 두 값은 이전 라인의 첫 번째 값에 현재 값을 더한 결과, 이전 라인의 마지막 값에 현재 값을 더한 결과이므로 최대를 구할 필요가 없다.