프로그래머스_정수 삼각형

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

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

 

• 접근법

문제는 Level 0 위치, 즉 숫자 피라미드의 맨 꼭대기부터 마지막 바닥 Level까지 내려갈 때 지나간 숫자들의 최대합을 구하여야 한다.  상위 Level에서 하위 Level로 내려갈 때는 일정한 규칙이 있다.

- 피라미드 형태에서 상위 Level의 왼쪽 아래, 오른쪽 아래, 두 위치로만 내려갈 수 있다.

이 조건이 이 문제를 동적 계획법(Dynamic Programming)으로 간단히 풀 수 있도록 해주었다.

 

• 코드 설명

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

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

- dp()함수는 level을 0 ~ 바닥까지 내려가는 일종의 for문을 대체한다.

- 이 함수는 level이 바닥을 찍으면 return된다.

- level 시작은 1부터다. (0이 맨 위)

- level을 하나씩 내려가면서 내려갈 때마다 해당 level의 값들을 상위 level값들을 참조하여 누적시킨다.

- 이때 문제의 규칙을 코드화 하면 이러하다

   -> Level의 n번째 값은 Level -1의 n-1번째 값과 Level -1의 n번째 값에서만 내려올 수 있다.

   -> 이 두 값중에 더 큰값에서 내려와야 해당 Level의 n번째에 도달했을 때 더 큰 누적값을 가질 수 있다.

   -> 위의 규칙을 그대로 코드로 작성한것이 위 dp() 함수의 for문이다.

- dp() 함수가 끝나면 triangle 리스트의 가장 마지막 리스트의 값들은 참조할 수 있는 2개의 값들 중 더 큰 값을 누적시키며 내려온 값일 것이므로 max() 함수를 이용해 가장 마지막 Level의 최대값을 구해준다. 이 값이 정답일 것이다.