파이썬 백준 1932번: 정수 삼각형

문제

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

1932번: 정수 삼각형

풀이

예제의 동작은 다음과 같다.

 

위 예제를 보면, 첫번째 값인경우, 중간값일 경우, 가장 끝의 값일 경우 를 나눠서 생각해야함을 알 수 있다. 

첫번째 값일 경우) 이전 행의 자신과 인덱스(0)가 같은 값을 그대로 더한다.

중간 값일 경우) 이전 행의 자신과 같은 인덱스와, 자신보다 하나 적은 인덱스를 자신과 더한 값을 계산한다. 이중 더 큰 값을 선택한다. 

끝의 값을 경우) 이전행의 자신보다 하나 적은 인덱스 값을 그대로 더한다. 

 

위에 맞춰 입력받은 이차원배열값을 업데이트하고, 마지막 행에서 가장 큰 값을 출력하면 된다!

import sys
n=int(sys.stdin.readline())
tr=[]
for i in range(n):
    tr.append(list(map(int,sys.stdin.readline().strip().split(' '))))
tr.append([0]*n) #모두 0으로 초기화

for i in range(1,n):
    for j in range(len(tr[i])):
        if j==0: # 0열인경우 윗줄의 결과를 그대로 더함
            tr[i][j]=tr[i-1][j]+tr[i][j]
        elif j==len(tr[i])-1: # 가장 끝의 경우 윗줄의 마지막열 결과를 그대로 더함
            tr[i][j]=tr[i-1][-1]+tr[i][j]
        else: # 중간 값일 경우 윗줄의 대각선값 중 큰 값을 선택
            tr[i][j]=max(tr[i][j]+tr[i-1][j-1],tr[i][j]+tr[i-1][j])