BOJ : 2579 계단 오르기

김가영·2020년 10월 8일
0

Algorithm

목록 보기
9/78
post-thumbnail

n_triangle : 삼각형의 크기
triangle : 삼각형
→ ex : [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
s_triangle : 삼각형 각 자리에서의 최댓값. 삼각형 위부터 계산된다.

i 열 j행 최댓값 = max(i-1 열 j행 최댓값, i-1 열 j-1행 최댓값) 이용

import sys
from collections import deque

n_triangle = int(sys.stdin.readline())
triangle = [ list(map(int,list(sys.stdin.readline().strip().split()))) for _ in range(n_triangle)]

s_triangle = []

for i, nums in enumerate(triangle):
    sums = []
    if i == 0:
        sums.append(triangle[0][0])
    else:
        for j,n in enumerate(nums):
            if j == 0:
                sums.append(n + s_triangle[i-1][0])
            elif j == len(nums)-1:
                sums.append(n + s_triangle[i-1][-1])
            else:
                sums.append(n+ max(s_triangle[i-1][j-1],s_triangle[i-1][j]))
    s_triangle.append(sums)

print(max(s_triangle[-1]))
profile
개발블로그

0개의 댓글