[BEAKJOON] 백준 1932번 : 정수 삼각형 - 파이썬

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

1932번: 정수 삼각형

 

 

이 문제는 DP로 푸는 문제이다.

해당 방법의 프로세스는 패턴을 찾을 수 있다.

양 사이드의 값은 위에 더할만한 값은 하나이고, 나머지는 그렇지 않기 때문에 가장 큰 값을 더해주면 된다.

# [0][0] = 7
# [1][0] = 7 + 3, [1][1] = 7+8
# [2][0] = 7+3+8, [2][1] = 7+3+1,

 

해결코드

import sys
num = int(sys.stdin.readline())
input_list = list()

for i in range(0, num):
    input_list.append(list(map(int, sys.stdin.readline().split())))

# [0][0] = 7
# [1][0] = 7 + 3, [1][1] = 7+8
# [2][0] = 7+3+8, [2][1] = 7+3+1,

result_list = list(input_list[0])
key = 0
for i in range(1, num):
    for j in range(len(input_list[i])):
        if(j == 0):
            input_list[i][j] += input_list[i-1][j]
        elif(i == j):
            input_list[i][j] += input_list[i-1][j-1]
        else:
            input_list[i][j] += max(input_list[i-1][j-1], input_list[i-1][j])

print(max(input_list[num-1]))