Programmers / 3단계 / 정수 삼각형 / python / 동적계획법(Dynamic Programming)

 

코딩테스트 연습 - 정수 삼각형 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

 

모범 답안

def solution(triangle):

    floor = len(triangle) - 1  # N층의 인덱스

    while floor > 0:  # N, N-1,...2, 1
        for i in range(floor):  # N번째 인덱스엔 0~N-> N+1개의 숫자가 있음
            # 바로 위층의 칸에 아래칸의 두개중 큰값을 더해줌
            triangle[floor-1][i] += max(triangle[floor][i], triangle[floor][i+1])
        floor -= 1  # 층하나 올라가기

    return triangle[0][0]