[프로그래머스] Lv3. 정수 삼각형

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

코드

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

풀이

• 삼각형의 제일 꼭대기부터 아래로 최대가 될 수 있는 누적합을 저장해나가야 한다.
• 좌, 우 로 내려갈 수 있다고 했으니 특정 꼭짓점, 예를 들어 3번째 라인 가운데 지점은 triangle[2][1]에 도달 할 수 있는 위치는 triangle[1][1], triangle[1][2]가 될 수 있다.
• 그리고 값을 채우는 연산을 하기 전에 2번째 라인 같은 경우에는 제일 꼭짓점 한 곳에서만 도달할 수 있으므로 미리 값을 넣어둔다.
• 또한 매 라인마다 양 끝은 도달할 수 있는 곳이 자신의 바로 전 라인 같은 인덱스이다. 그러므로 양 끝은 매 라인 시작마다 값을 넣어둔다.
• 남는 꼭짓점에 대해서 도달할 수 있는 값의 최대값을 구하는 것은 max()를 이용해서 구할 수 있다.
• 마지막 라인의 최댓값을 리턴한다.