[Programmers] 정수 삼각형

 

 

[문제 설명]

 

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

 

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

 

 

[풀이 과정]

 

동적 계획법(Dynamic Programming)으로 분류되어 있는 문제다.

 

'동적 계획법'이란 무엇인가? 

 

동적 계획법 : 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

라고... 위키백과에서는 말하는데.. 이해가 가는가? 학술적인 어휘와 딱딱한 설명은 이해를 방해하고 다가가기 어렵게 한다.

 

본인이 생각하는 동적 계획법이란 불필요한 변수 혹은 연산을 생략하여 수행시간을 최소화 하는 것이다.

 

필자의 경우는 문제가 동적 계획법으로 분류되어 있음을 보면 'ㅇㅎ! 모두 계산하면 안풀리게 끔 만들어 놓았구나!, 그렇다면 어떤것을 버리면 좋을까?' 하고 생각한다.

그리고 역시 문제에서는 완전탐색으로는 시간초과를 걸리게 끔 해놓고, 변수 생성을 덜 해도 될 만한 여지를 남겨놓는다.

 

그렇다면 이 문제에서 버려야 할 것은 무엇일까?

 

필자는 '큰 값만 취급함'과, '순회의 방향'이라고 생각한다.

 

문제는 이어지는 경로 중 숫자의 합이 가장 큰 것을 요구한다.

 

왼쪽 아래의 삼각형을 예로 들자면

 

  2

4  5

 

2+4와 2+5중에 다음 연산에 다시 쓰이는 것은 2+5 일텐데 굳이 2+4를 계산하여 변수로 추가 하여야 하는가?

 

그리고,

 

전위 순회에서는 아래와 같이 계산해야하는 양이 늘어남과 동시에, 위의 방식처럼 큰 값만 취급하기가 어렵다.

'''

[7]

[7+3, 7+8]

[7+3+8, 7+3+1, 7+8+1, 7+8+0]

[7+3+8+2, 7+3+8+7, 7+3+1+7, 7+3+1+4, 7+8+1+7, 7+8+1+4, 7+8+0+4, 7+8+0+4]

'''

 

후위순회를 하며 큰 값만 취급하여 연산을 거듭하는 것이 이 문제 해결의 키인듯하다.

 

def solution(triangle):
    triangle = triangle[::-1]

    current = triangle[0].copy()
    triangle.remove(triangle[0])

    for arr in triangle:
        temp = []
        for i in range(0, len(current)-1):
            temp.append(max(current[i],current[i+1]) + arr[i])
        current=temp
        
    return current[0]