[백준] 1932번 정수 삼각형

단계별로 풀어보기 동적계획법1의 6단계 문제

1932번: 정수 삼각형

이렇게 bfs로 풀어서 제출했는데

n = int(input())
from sys import stdin
li = []
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
sum = []
import collections
q = collections.deque()
q.append((0, 0, li[0][0]))
while q:
    cur = q.popleft()
    if cur[0] == n - 1:
        sum.append(cur[2])
    else:
        q.append((cur[0] + 1, cur[1], cur[2] + li[cur[0] + 1][cur[1]]))
        q.append((cur[0] + 1, cur[1] + 1, cur[2] + li[cur[0] + 1][cur[1] + 1]))
print(max(sum))

메모리 초과로 실패

 

그래서 삼각형 아랫쪽부터 위로 올라오는 방식으로 동적계획법을 사용한 코드로 바꾸었다.

n = int(input())
from sys import stdin
li = []
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
    li[i].extend([0] * (n - 1 - i))
for i in range(n - 2, -1, -1):
    for j in range(i + 1):
        li[i][j] = max(li[i][j] + li[i + 1][j], li[i][j] + li[i + 1][j + 1])
print(li[0][0])

성공