[백준,Python]1932번 정수 삼각형(DP,dynamic programming)

백준 1932번 정수 삼각형(DP)문제 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

정수 삼각형에서 이어지는 경로로 탐색했을 때 모든 노드 수의 합의 최댓값을 구하는 문제를 리뷰하겠습니다.

 

Dynamic Programming으로 푸는 문제이며, 하나씩 depth을 증가시키며 이어지는 경로로 내려가며 탐색을 진행해야 하므로 배열 arr이 있다고 하면, arr[i][j] = arr[i][j] +( arr[i-1][j] or arr[i][j-1]중의 최댓값)원리를 생각하고 문제를 풀어보았습니다.

 

#첫째 줄에 삼각형의 크기 n을 받아서 둘째줄 부터 n+1번째 줄까지 정수 삼각형을 그리고 경로 안의 합의 최대를 출력.

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

side=2 # 삼각형이 되려면 최소 2*2이니까 
for i in range(n):
    result.append(list(map(int,input().split())))
for i in range(1,n): # 맨 위의 값은 무조건 더해야 하므로 1부터 시작.
    for j in range(side):
        if j==0: #즉, 가장 왼쪽 줄일때,
            result[i][j] +=result[i-1][j]
        elif i==j: # 가장 오른 쪽 줄일 때
            result[i][j] +=result[i-1][j-1]
        else: # 가운데
            result[i][j] +=max(result[i-1][j],result[i-1][j-1])
    side+=1 # 다음 줄은 1증가하므로
print(max(result[n-1]))

* 풀어서 설명을 하면,

 삼각형 행렬이 만들어졌을 때 2행부터 값을 1행값을 더한 것으로 수정하고 3행은 증가된 2행값을 더한 것으로 수정을 반복하면 n행의 값은 n-1행+n-2행 +...+1행까지의 값을 더한 결과의 행렬이 나오게 됩니다.

따라서, max함수를 이용해 max(result(n-1))을 해주면 경로 중의 최댓값이 나오게 됩니다.(index는 0부터 시작이므로n-1입니다)