[백준/python] 1932번 : 정수 삼각형

문제

        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번째 줄까지 정수 삼각형이 주어진다.

 

출력

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

 

정답

import sys
n = int(sys.stdin.readline())
number = []
for i in range(n):
    number.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            number[i][0] += number[i - 1][0]
        elif j == i:
            number[i][j] += number[i-1][j-1]
        else:
            number[i][j] += max(number[i - 1][j - 1], number[i - 1][j])

answer = 0
for k in range(n):
    if answer < number[n - 1][k]:
        answer = number[n - 1][k]

print(answer)

---

아래로 내려오면서 현재 위치의 수를 인접한 위의 숫자들 중 큰 값과 더한 값으로 대체한다.

맨 마지막 줄까지 내려오면 마지막 줄에 있는 수 중 가장 큰 값을 출력한다.

 

예를 들어 현재 위치가 두번째 줄에 있을 경우,

인접한 7을 더한 값인 10과 15로 대체한다.

 

현재 위치가 세번째 줄의 2번째 값인 1에 있을 경우,

인접한 10과 15 중 15가 더 크기때문에 15를 더한 값인 16으로 대체한다.

 

if j == 0:
	number[i][0] += number[i - 1][0]
elif j == i:
	number[i][j] += number[i-1][j-1]
else:
	number[i][j] += max(number[i - 1][j - 1], number[i - 1][j])

반복문을 수행하면서 현재 위치의 수 number[i][j]가 맨 앞이나 맨 뒤에 있을 경우,

인접한 위의 숫자가 하나밖에 없으므로 주의해야한다.