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

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

나의 풀이 

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(i+1):
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
                
            
    return max(triangle[-1])

접근법 및 코드 설명

삼각형의 맨 위부터 한 높이씩 내려오며 각 원소 값에 올 수 있는 최댓값을 계속해서 업데이트 해주는 방식으로 문제를 해결할 수 있다.

 

최댓값을 업데이트 하는 과정을 세 가지로 나눌 수 있는데, 우선 어느 층이든 맨 왼쪽, 맨 오른쪽 값, 즉 인덱스가 0이거나 h(높이)인 경우는 다른 수와 비교할 것 없이 바로 직전 층의 인덱스가 0인 값과 h(높이)인 값을 넣어주면 된다. (층은 편의상 거꾸로 세준다.)

 

즉, 3번째 층의 0번 인덱스의 값은 2번째 층의 0번 인덱스의 값이 들어와야하며, 3번째 층의 3번째 값(2번 인덱스 값)은 2번째 층의 1번째 값(1번 인덱스)이 와야한다.

 

따라서, 해당 경우를 각각 j == 0 일 때와 j == i 일 때로 나누어 예외처리를 해준 후, 나머지 값들에 대해선 해당 위치에 들어올 수 있는 두 개의 값을 비교한 후, 더 큰 값을 삽입하는 방식으로 처리해준다.

 

이후, 마지막 층(맨 아래 층)에 있는 값들 중 가장 큰 값을 리턴해주면 정답을 구할 수 있다.