[프로그래머스] 정수 삼각형 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 

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

 

간단한 DP 문제이다.

맨 꼭대기에서 양 옆 대각선으로 더해 내려갈때 최대값을 구하는 문제이다.

점화식이랄것도 없다.

현재 점에서 양 옆 위 대각선의 값 중 큰 값을 현재 값에다 더해서 내려가면 된다.

주의할 점이라면 위에서 아래로 내려가면서 위의 대각선을 확인하므로 1부터 시작하고

양끝 점은 대각이 하나만 있으므로 처리해주면 된다.

 

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