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

문제

프로그래머스

알고리즘

- DP 문제로 규칙을 찾는다.

- i번 triangle부터 보게 되면 i-1번째 triangle의 같은 위치와 그 이전 위치 값 중 큰 값을 받으면 된다.

- 위 규칙을 편리하게 하기 위해 trianlge 리스트 인덱스 안에 각각 0을 추가한다.

코드

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

github

 

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법(Python)