[백준] 1932번 정수 삼각형(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 1932번 문제입니다. (solved.ac)기준 실버 1 문제입니다.

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

1932번: 정수 삼각형

문제 접근

처음에는 하나 하나 어떻게 비교하나 생각을 했었는데.. 생각을 해보니 위에서부터 아래로 내려가면서 더 큰 값을 더해주고 맨 마지막 줄에서 가장 큰 값을 출력하게 만들면 되는 문제였습니다..! 

 예를 입력 1로 예를 들면 두번째 줄에 있는 3, 8은 선택의 여지없이 7을 받아 각각 10과 15가 되고

세 번째 줄에 있는 8, 1, 0 중 가장 왼쪽에 있는 8은 반드시 10(7+3)을 받아야 하고 중간에 있는 1은 10(7+3)과 15(7+8)중 더 큰 값인 15를 받고 가장 우측에 있는 0은 반드시 15(7+8)을 받아야 합니다. 이와 같은 논리로 마지막 줄 까지 내려간 후 마지막 줄에서 가장 큰 값을 출력하면 문제에서 요구하는 답이 출력되게 됩니다!

아래 예시코드에서는 인덱스 계산이 헷갈리지 않도록 [1][1]부터 계산을 진행하도록 설계하였습니다.

ex) tri[1][1] = 7

정답 코드

n = int(input())

tri=[[0] * (n+1) for _ in range(n+1)]

for i in range(1, n+1) :

    input_data = input().split()

    for j in range(0, len(input_data)):
        tri[i][j+1] = int(input_data[j])

if n >= 2 :
    tri[2][1] += tri[1][1]
    tri[2][2] += tri[1][1]

if n >= 3 :
    for i in range(3, n + 1):

        for j in range(1, i + 1):

            if j == 1 or j == i + 1:
                tri[i][j] += tri[i - 1][j]
            else:
                tri[i][j] += max(tri[i - 1][j - 1], tri[i - 1][j])

print(max(tri[n]))