백준 1932 : 정수 삼각형 (파이썬)

문제 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

정수 삼각형

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

57640

32111

24045

58.623%

문제

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

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

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

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

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1

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

예제 출력 1

30

---

코드

# https://teching.tistory.com/
import sys
n = int(sys.stdin.readline().rstrip())
memo = [0]*n
for l in range(1,n+1):
    nums = list(map(int,sys.stdin.readline().split()))
    tmp = [0]*l
    for i in range(l):
        if i == 0: tmp[i] += memo[i]+nums[i]
        else:
            tmp[i] = max(nums[i]+memo[i-1], nums[i]+memo[i])
    memo[:l] = tmp
print(max(memo))

해설

문제의 규칙이 맨 위부터 하나씩 선택하며 아래로 내려올 때 대각선 왼쪽 또는 대각선 오른쪽에 있는 것만 선택해 가며 내려올 수 있다.

이는 반대로 말하면 현재 층에서 어떠한 숫자를 선택했을 때 그 왼쪽 대각선 위 혹은 오른쪽 대각선 위의 숫자를 선택했을 경우, 두 가지가 올 수 있다는 소리다.

또한 해당 층의 결과가 그 위층까지의 합에는 영향을 미치지 않으므로 이전 층까지의 결과는 계속 저장을 해줘서 불필요한 계산을 하지 않도록 한다. 즉, 새로운 층을 탐색할 때 각 숫자별로 새롭게 생기는 두 가지 경우의 수만 지속적으로 확인해주면 된다.

이는 동적계획법의 타뷸레이션 기법을 활용한 방법이다.

타뷸레이션에 대한 내용은 https://teching.tistory.com/89 포스트에서 정리를 해두었으니 참고 바란다.

동적 계획법 (파이썬)