[웅's 프로그래머스] 정수 삼각형 - 파이썬(python) 풀이

이해를 돕고자 그림을 그려봤다... 

목적은 정수 삼각형과 같은 리스트를 만드는 것인데, 점점 아래로 내려갈 수록 위의 값과의 합을 저장하여 리스트르 만드는 것이었다. 예시로 그럼에 위 세 줄만 뽑아서 만들어봤다

 

문제는 가운데에 있는 값의 경우 왼쪽에서 내려온 값과 오른쪽에서 내려온 값 2가지의 경우가 생긴다는 것이다. 문제에서는 가장 큰 값을 구하는 것이 문제이므로 두 값을 비교한 후 더 큰 값을 저장하기로 한다.

 

이때 그림에서도 볼 수 있듯이 오른쪽 값은 항상 자기와 같은 idx 값을 가지고 왼쪽 값은 idx-1 값을 구하면 된다.

def solution(triangle):
    height = len(triangle)
    list = [0]*height    
    for i in range(height):
        if i==0:
            list[0] = triangle[i]
            continue
        xList = list[i-1]
        temp = []
        for j in range(i+1):
            left, right = 0, 0

            if(j-1>=0):
                left = xList[j-1] + triangle[i][j]

            if(j<len(xList)):
                right = xList[j] + triangle[i][j]

            if(left>right):
                temp.append(left)

            else:
                temp.append(right)
        list[i] = temp

    return max(list[height-1])