문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

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

출력

30

memo = {}
def f(n):
    if n in memo:
        return memo[n]
    else:
        output = []
        ex = f(n-1)
        if len(ex) < 2:
            output.append(ex[0] + tri_numbers[n-1][0])
            output.append(ex[0] + tri_numbers[n-1][1])
        else:
            output.append(ex[0] + tri_numbers[n-1][0])
            k = 0
            for i in tri_numbers[n-1][1:-1]:
                tmp = []
                for j in ex[0+k:2+k]:
                    tmp.append(i + j)
                output.append(max(tmp[0], tmp[1]))
                k += 1
            output.append(ex[-1] + tri_numbers[n-1][-1])
        memo[n] = output
        return output

num = int(input(''))

tri_numbers = []
for i in range(num):
    i = [int(x) for x in input('').split()]
    tri_numbers.append(i)

memo[1] = tri_numbers[0]

print(max(f(num)))

코드 리뷰

1. 재귀함수와 메모화 사용

• root에서 아래 노드로 내려가면서 비슷한 과정을 진행 하기 때문에 재귀함수를 사용하였다.
• 메모화를 통해 재귀함수의 단점을 보완

2. 중복으로 더해지는 부분을 제거

• 이 부분에서 가장 많은 시간을 소비
• 처음에는 중복되는 부분을 제거하지 않고 모든 경우의 수를 매칭시키려 하여 코드가 많이 복잡해지고 패턴을 찾기 어려웠음
• 겹치는 노드는 그 노드까지의 합이 큰 경우만 살려서 문제 해결
  (예 위의 문제에서 3번째 줄 1번까지 가는 경로는 7-> 3-> 1 과 7 -> 8 -> 1 두 가지다. 그 둘중 두 번째 경우로 가는 것이 경로의 합이 크므로 두번째만 살려서 다음 시퀀스를 진행
• 단 가장 처음과 마지막은 중복되지 않는 노드이기때문에 이 부분들은 for문에서 제외.(처음 요소 -> for문(중간 요소들) -> 마지막 요소 순으로 진행)