알고리즘: 백준 1932번 정수 삼각형 (feat. Python)

---

 

최적 부분 구조와 중복되는 부분이 보인다. 다이나믹 프로그래밍으로!

 

 

 

점화식: 

 

 

n 번째 줄 0번째까지의 합 =   n - 1번째 줄 0번째까지의 합 + n 번째 줄 0번째 값

 

n 번째 줄 1번째까지의 합 =   max(n - 1번째 줄 0번째까지의 합, n - 1번째 줄 1번째까지의 합) + n번째 줄 1번째 값

 

n 번째 줄 2번째까지의 합 =   max(n - 1번째 줄 1번째까지의 합, n - 1번째 줄 2번째까지의 합) + n번째 줄 2번째 값

 

             ...

 

 

n 번째 줄 n - 1번째까지의 합 = max(n - 1번째 줄 n - 2번째까지의 합, n - 1번째 줄 n - 1번째까지의 합) +

n번째 줄 n - 1번째 값

 

n 번째 줄 n번째까지의 합 =  n - 1번째 줄 n - 1번째까지의 합 + n 번째 줄 n번째 값

 

 

 

 

∴ n번째 줄까지 더했을 때의  최대값 = 

 

max( n번째 줄 0번째까지의 합, n번째 줄 1번째까지의 합, ...,  n번째 줄 n - 1번째까지의 합, n번째 줄 n번째까지의 합)

 

 

import sys
input = sys.stdin.readline # 더 가볍고 빠른 입력을 받기 위해서

n = int(input())

array = []  # 입력한 값을 받아올 배열
table = []  # 최대값들을 저장할 배열


for i in range(n):
    array.append([0 for _ in range(i + 1)])  # 삼각형 모양의 배열을 만들어준다
    table.append([0 for _ in range(i + 1)])


for i in range(n):
    array[i] = list(map(int, input().split()))  # 받아온 입력 값들을 array에 넣어주기 


for i in range(n):

    if i == 0:
        table[i][i] = array[i][i]
   
    else:

        for j in range(0, i + 1):
        
            if j == 0:             # 가장 왼쪽 값을 지정하기 위한 table 값은 한개!
                table[i][j] =table[i - 1][j] + array[i][j]
                
            elif i == j:           # 가장 오른쪽도 마찬가지! 
                table[i][j] = table[i - 1][j - 1] + array[i][j]
                
            else:                  # 그 외는 max를 이용해서 값을 지정해준다.
                table[i][j] = max(table[i - 1][j], table[i - 1][j - 1]) + array[i][j]



print(max(table[n - 1]))

 

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30