[Baekjoon] 1932번 : 정수 삼각형 (Python)

[Baekjoon] 1932번 : 정수 삼각형 (Python)

 

목차

 

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

1932번: 정수 삼각형

Python

 

방법 1 - 메모리 38948KB / 시간 212ms / 코드 길이 395B

 

DP를 위한 Programming을 사용하여 풀 수 있다.

처음과 끝에 있는 경우는 윗 줄의 한 가지만을 확인하기 때문에 별도의 if문을 제기한다.

나머지는 상위 좌우의 비교를 하여 max를 가지고 점진적인 저장을 한다.

최종적으로 마지막 줄의 최댓값을 구하면 끝이다.

 

n = int(input())
l = [list(map(int, input().split())) for i in range(n)]

t = [[0]*i for i in range(1,n+1)]
t[0][0] = l[0][0]

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            t[i][j] += l[i][j] + t[i-1][0]
        elif j == i:
            t[i][j] += l[i][j] + t[i-1][j-1]
        else:
            t[i][j] += l[i][j] + max(t[i-1][j-1], t[i-1][j])

print(max(t[-1]))

 

속도를 빠르게 하고싶다면

import sys

sys.stdin.readline을 활용