프로그래머스 레벨 3 정수삼각형

위에서부터 시작해서 거쳐간 숫자의 합이 가장 큰 경우를 return해야하는 문제

전형적인 dp문제인듯

원래 이런문제들 보면 top-down방식으로 푸는걸 선호하지만 밑에서 부터 둘 중 최댓값을 더해주는 방식도 효율적일것 같아서 bottom-up 방식으로 풀어보았다.

가독성과 편리성을 위헤서 그냥 triangle.reverse() 해주었음

def solution(triangle):
    triangle.reverse()

    for i in range(len(triangle)-1):
        for j in range(len(triangle[i])-1):
            triangle[i+1][j]+=max(triangle[i][j],triangle[i][j+1])
        
    return triangle[-1][0]

삼각형 높이가 최대 500이라 대충 시간복잡도는 500x500x2 해서 아무리 많이 나왇 50000 미만 정도 나올거라고 예상했는데, 효율성 테스트에서 생각보다 실행시간이 오래걸림,

그래서 len함수 문제인가 싶어서 range 범위도 변수로 선언해준다음 반복문 하나 실행되면 변수-=1 해주는 방식으로 해봤는데 딱히 변하는건 없었음.

다른사람들 코드 넣어봤더니 결과는 같음; 그냥 이게 맞는듯