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

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

다이나믹 프로그래밍을 사용하는 문제라고 합니다. 

저는 다르게 접근한 것 같은데 우선 문제부터 요약해 보도록 하겠습니다. 

다음과 같은 삼각형에서 위에서 부터 가장 아랫층 까지 쭉 타고 내려오는 경로가 있으면, 그 경로에서 가장 커지는 값을 return 하는 문제입니다. 

 

즉 solution(triangle)에 

triangle : 삼각형의 정보

가 주어질 때, 거쳐간 경로의 숫자의 최댓값을 return해야 합니다. 

 

<Solution>

아이디어는 다음과 같습니다.

 

밑에서 두번째 층에서 출발해서 그 층에서 한층씩 위로 for loop를 진행시킵니다. 

해당하는 mini triangle (위의 빨간 글씨에서 2,4,5 처럼) 에서 더 큰 값으로 전체 triangle을 update 시킵니다. 최종적으로 가장 꼭대기 층에 남는 숫자가 최대값입니다. 

 

실제 구현은 아래와 같습니다. 

def solution(triangle):
    if len(triangle) == 1:
        return triangle[0][0]

    time = len(triangle)-1
    list_ = triangle[len(triangle)-2][:]

    for i in range(time-1,-1,-1):
        new_list = []
        for index,e in enumerate(triangle[i]):
            new_list.append(max(e+triangle[i+1][index], e+triangle[i+1][index+1]))
        list_ = new_list
        triangle[i] = new_list

    return new_list[0]