[백준] 1932 정수삼각형 파이썬 풀이

문제

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

내 풀이

첫 번째 풀이

메모리 초과로 인해서 실패했다.

from collections import deque
N = int(input())
tri = []

for _ in range(N) :
  tri.append(list(map(int, input().split())))

q = deque()
dp = [0 for _ in range(N)]
q.append([0,0])
while q :
  curDepth, curIdx = q.popleft()
  if curDepth == 0 :
    dp[curDepth] = tri[curDepth][curIdx]
  else :
    dp[curDepth] = max(dp[curDepth], tri[curDepth][curIdx] + dp[curDepth - 1])
  nextDepth = curDepth + 1
  if nextDepth >= N :
    continue
  nextIdx = [curIdx, curIdx + 1]
  q.append([nextDepth, nextIdx[0]])
  q.append([nextDepth, nextIdx[1]])

print(dp[N-1])

두 번째 풀이

바텀업 방식으로 다음층에 있는 max 값은 결국 아래층에서 올 수 있었던 2개의 값과 합한 값중 하나라는 점을 이용해서 0층까지 올라오면 된다.

N = int(input())
tri = []

for _ in range(N) :
  tri.append(list(map(int, input().split())))

for depth in range(N - 1, -1, -1) :
  if depth == N - 1 :
    continue
  COLUMN = depth + 1
  for c in range(COLUMN) :
    tri[depth][c] = max(tri[depth+1][c] + tri[depth][c], tri[depth+1][c+1] + tri[depth][c])

print(tri[0][0])