💡 문제 해결 아이디어

내가 생각한 아이디어

• 삼각형의 이전 줄에서 다음 줄로 갈 때, 양 끝을 제외하고는 좌측상단이나 우측상단으로부터 내려올 수 밖에 없다.
• 따라서, 좌측상단과 우측상단 중에서 더 숫자가 큰 쪽을 따라서 내려왔다고 판단하고, 해당 위치에 누계를 저장시키면 된다.
  
• 예시에서 두번째 줄의 [3, 8]은 "양 끝"이기에 당연히 7을 거쳐서 누계가 [10, 15]가 되어야 한다.
• 그리고 세번째 줄의 [8, 1, 0]에서 "양 끝이 아닌" 1은 좌측상단 10과 우측상단 15중에서 15를 따라서 왔다고 판단하면 되기에, 누계가 [18, 16, 15]가 된다.

위와 같이 동적으로 계산하면, 불필요한 n!의 계산을 하지 않고, O(n)으로 알뜰하게 계산이 된다.

💻 작성된 코드

def solution(triangle):
	# 반복문을 통해, 한 줄씩 가장 큰 경우를 계산해 나간다.
    for i in range(len(triangle)-1):
        prev = triangle[i]
        now = triangle[i+1]
        for j in range(i+2):
        	# 왼쪽 끝이면, 이전 줄의 왼쪽 끝을 따라 누계
            if j == 0: now[j] += prev[0]
            # 오른쪽 끝이면, 이전 줄의 오른쪽 끝을 따라 누계
            elif j == i+1: now[j] += prev[i]
            # 양끝이 아니면, 좌측상단과 우측상단 중 더 큰 값을 따라 누계
            else: now[j] += max(prev[j-1], prev[j])
    # 마지막 줄에서 제일 큰 값을 반환
    return max(triangle[-1])