백준 1932 - 정수 삼각형

문제 링크

Code

import sys
from collections import deque
read = sys.stdin.readline

tri = []
n = int(read())
for _ in range(n):
    tri.append(list(map(int, read().split())))

ans = deque([tri[0][0]])
for i in range(1, n):
    for j in range(i):
        num = ans.popleft()
        if j==0:
            ans.append(num+tri[i][j])
        else:
            ans[-1] = max(ans[-1], num+tri[i][j])
        ans.append(num+tri[i][j+1])
print(max(ans))

애로사항

  • 분할해서 정복하는 방법으로 해줬더니 해결할 수 있었다.
  • else 부분이 코드의 핵심 부분이다.

좋은 웹페이지 즐겨찾기