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

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

 

이 문제는 위 사진과 같이 크기가 N인 정수 삼각형을 입력받아,
맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때
이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램이다.

 

 

import sys

input = sys.stdin.readline

N = int(input()) # 삼각형의 크기
A = []

# 정수 삼각형 입력받기
for i in range(N):
    arr = list(map(int, input().split()))
    A.append(arr)

# 합배열 삼각형 만들기
for i in range(1, N):
    
    A[i][0] += A[i-1][0] # 왼쪽 끝값 부모값 더하기
    A[i][-1] += A[i-1][-1] # 오른쪽 끝값 부모 값 더하기
    
    for j in range(1, i):
        A[i][j] += max(A[i-1][j], A[i-1][j-1]) # 부모값 중 큰 값 더하기

print(max(A[-1])) # 최장 경로 print

 

 

[문제풀이]

---

 

가장 최장 경로를 구하려면 모든 경로를 탐색해서 가장 최장 경로를 구해야 한다.

그를 구하기 위해서 합배열 삼각형을 만든다.

 

 

자식이 선택할 수 있는 부모의 값은 2개, 그 중 가장 큰 부모의 값을 더한다.

그럼 최종적으로는 가장 큰 경로 n개가 맨 밑의 노드에 저장되게 된다.

 

 

그럼 그 중 가장 큰 값을 선택하면, 최장 경로가 된다.