[백준 1932] Python - 정수 삼각형

이 문제 유형도 풀어본 유형이라서 쉬웠당

규칙만 잘 찾아내면 스무스 ^_^

 

위 삼각형을 예시로한다면,

 

arr[0][0] = 7

 

arr[1][0] = 3 + arr[0][0]         arr[1][1] = 3 + arr[0][0]

 

arr[2][0] = 8 + arr[1][0]         arr[2][1] = 1 + max( arr[1][0] , arr[1][1] )             arr[2][2] = 0 + arr[1][1]

 

 

규칙이 보이지 않나욤 ??

 

처음과 끝은 무조건 한칸 위의 맨앞 맨뒤의 것을 가져오는 반면,

그 외의 것은 대각선 왼쪽, 오른쪽 중에 더 큰 값을 가져옴 !!!

 

이 식을 그대로 적용시키면 끄읕 !

n = int(input())
arr=list()
for _ in range(n):
    arr.append(list(map(int,input().split())))

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