[백준] 1932번 정수 삼각형 [Python] - 다이나믹

아래 그림 같은 정수 삼각형이 주어질 때,

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

 

 

맨 위에 있는 꼭짓점부터 바로 아래에 있는 숫자 중 하나$($아래층의 대각선 왼쪽 또는 대각선 오른쪽$)$를 골라서 내려올 때, 합이 최대가 되는 경로의 그 합을 구하는 문제 

 

문제

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

출력

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

 

정수 삼각형을 한줄씩 입력 받을 때,

왼쪽 대각선으로만 내려가는 경우, 가운데 경우, 오른쪽 대각선으로만 내려가는 경우로

현재 입력 받은 줄의 각 요소를 목적지로 했을 때, 최대 합이 되도록하는 경로의 수의 합을

graph에 저장하며 업데이트 한다.

 

마지막 줄까지 모두 입력 받아 업데이트를 하면 그 중 최댓값을 출력하면 된다.

from sys import stdin
n = int(stdin.readline())
graph = [int(stdin.readline())]

for i in range(n-1):
    new = list(map(int, stdin.readline().split()))
    graph = [new[0] + graph[0], *[new[j] + max(graph[j-1], graph[j]) for j in range(1, i+1)], new[i+1] + graph[i]]

print(max(graph))

 

위와 같은 로직이지만, graph를 2차원 배열로 활용해서 좀 더 풀어쓴 코드

정수 삼각형의 모양대로 graph를 생성하고

왼쪽 대각선으로만 내려가는 경우, 가운데 경우, 오른쪽 대각선으로만 내려가는 경우로 나누어서 

graph에 경로의 최대 합 업데이트하는 코드

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

for i in range(n-1):
    graph[i+1][0] += graph[i][0]
    graph[i+1][i+1] += graph[i][i]
    
    for j in range(1, i+1):
        graph[i+1][j] += max(graph[i][j-1], graph[i][j])

print(max(graph[n-1]))

 

왼쪽 대각선으로만 내려가는 경우, 가운데 경우, 오른쪽 대각선으로만 내려가는 경우 구분 없는 코드,,

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

ans = [[] for _ in range(n)]
ans[0] = [graph[0][0]]
for i, row in enumerate(graph[1:]):
    for j, m in enumerate(row):
        ans[i+1].append(max(ans[i][max(0, j-1)], ans[i][min(j, i)]) + m)

print(max(ans[n-1]))

 

예제 입력 1 

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

예제 출력 1 

30