[백준] 1932번 : 정수 삼각형 (파이썬)

문제

나의 답안

import sys
input = sys.stdin.readline

n=int(input())
arr=[]

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

for i in range(1,n):#합 구하기
    for j in range(len(arr[i])):#각 1차원 배열 접근
        if j==0:#왼쪽 첫번째
            arr[i][j]+=arr[i-1][j]
        elif j==i: #오른쪽 끝
            arr[i][j]+=arr[i-1][j-1]
        else: #가운데
            arr[i][j]+=max(arr[i-1][j-1],arr[i-1][j])
        
print(max(arr[n-1]))#n개의 합 중 가장 큰 값

접근 방법

• 다음과 같은 삼각형에서 삼각형의 아랫줄부터 보는 것이 이해하기 편하다.
• 가장 아랫줄을 보면
  (왼쪽) arr[4][0]=4+arr[3][0]
  (오른쪽) arr[4][4]=5+arr[3][3]
  (나머지 숫자)
  arr[4][1]=5+max(arr[3][0], arr[3][1])
  arr[4][2]=2+max(arr[3][1], arr[3][2])
  arr[4][3]=6+max(arr[3][2], arr[3][3])
  이 된다.
• 양쪽 끝은 바로 위의 숫자를 더할 수 있고, 나머지 숫자들은 왼쪽 오른쪽 중 큰 값을 골랐을 때 최대가 되기 때문이다.
• 따라서 위의 식을 기준으로 코드를 짜면 된다.
• 반복문으로 각 줄의 합을 하나씩 구해 전부 더한 값을 arr[i][j]에 저장하고, 마지막 출력문에서 각 줄(n개)의 합 중 최대값을 출력해주면 된다.