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

          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5

 

 

 

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

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

 

 

위 형태로 Triangle을 구성하면 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 가 된다. 먼저 문제를 풀기 전에 Index Error가 발생하지 않도록 각 행의 양 옆에 [0]을 Padding 해준다.

 

        0   7   0
      0   3   8   0
    0   8   1   0   0
  0   2   7   4   4   0
0   4   5   2   6   5   0

 

그런 다음, 시작 지점에서 한 단계씩 내려가면서 최대 값을 찾아가면 된다. 한 Step 을 수행했을 때 예시는 아래와 같다.

        0   7   0
      0   10   15   0
    0   8    1    0    0
  0   2    7    4    4   0
0   4   5    2    6    5    0

 

다음 단계는, 이전 단계에서 하던 방식과 동일하고, 다음 Step에서 최댓값으로 대체하는 것이다.

        0   7   0
      0   10   15   0
    0   18   16   15   0
  0   20   25   20   19   0
0   24   30   27   26   24    0

 

 

위 과정을 전체 코드로 표현하면 아래와 같이 작성할 수 있다.

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

 

문제의 목적은 최댓값을 찾는 것이기 때문에, 가장 바닥에 있는 행을 가지고 와서, 해당 행의 최댓값을 반환하는 것이다.