[프로그래머스] 👨‍🏫 정수 삼각형 / python

👨‍🏫 정수 삼각형 문제 풀어보기

😃 나의 코드

def solution(tri):
    m_lst = []
    for row in tri:
        lst = []
        if len(m_lst) == 0:
            lst.append(row[0]);
        else:   
            for idx, num in enumerate(row):
                if idx == 0:
                    lst.append(m_lst[-1][idx] + num)
                elif idx == len(row)-1:
                    lst.append(m_lst[-1][-1] + num)
                else:
                    lst.append(max(m_lst[-1][idx-1],m_lst[-1][idx]) + num)
        m_lst.append(lst)
    return max(m_lst[-1])

DP(Dynamic Programming, 동적계획법)을 이용해 해결한 문제입니다. DP의 계획에 따라 전체 문제를 작은 문제로 나누어서 풀겠습니다. 주어진 삼각형이 아닌 그보다 작은 삼각형에 대한 문제를 풀어서 그 크기를 점점 키워서 주어진 삼각형까지 나아갑니다.

m_lst라는 새로운 배열을 만들어 이 곳에는 아래로 거쳐간 숫자의 합이 가장 큰 경우의 결과값만 저장하도록 코드를 짭니다. 다음으로 DP의 다음 특징인 다른 시행의 결과값을 사용하여 작은 삼각형에서의 특정 위치의 합의 최대값을 이용하여 다음 최대값을 구합니다. 이런 식으로 마지막까지 구한 뒤 max(m_lst[-1])을 이용하여 삼각형의 맨 아래칸의 최대값 배열중 가장 큰 값을 반환하면 문제가 마무리됩니다.

Written with StackEdit.