[DP] 정수 삼각형

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

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

 

예전에는 dp문제가 어려웠는데, 그렇게 어렵지도 않은 것 같다.
효율성 테스트도 한번에 통과했다.

 

위와 같이 삼각형의 일부분에 대해, 1을 지나가는 경우는, 3을 지나고 1을 지나는 경우와 8을 지나고 1을 지나는 경우 두가지밖에 없다.

즉 삼각형이 양 끝의 경우에 대해 if문으로 처리해주고,

그 가운데들에 대해서는 두 가지경우중 더 큰 경우를 선택하면서 삼각형테이블을 채우다보면, 맨 마지막 행중 최대값이 곧 답이 된다.

 

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