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

문제

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

코드

T = int(input())
q = []

for i in range(T):
    q.append(list(map(int,(input().split()))))

for i in range(1,T):
    for j in range(len(q[i])):
        if j==0: # 맨왼쪽
            q[i][j] += q[i-1][j]
        elif j==i: # 맨오른쪽
            q[i][j] += q[i-1][j-1]
        else: # 가운데
            q[i][j] += max(q[i-1][j], q[i-1][j-1])

print(max(q[T-1]))

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

#      7
#    10 15
#   18 16 15
#  20 25 20 19
# 24 30 27 26 24

 

코드설명

최종으로 합이 최대값 이여야 하기 때문에 바로앞에 큰값만 고른다고 해결되지 않는다.

dp를 이용해 값을 저장해 그 중 가장 큰 값을 고르면 된다.

q 이중배열에 q[1] 부터 q[T-1] 까지 더하면서 이동한다.

 

삼각형에서 가장 왼쪽과 오른쪽은 위에 더할 선택지가 하나이기 때문에 그냥 더해주고

가운데 값들은 두개중에 큰값을 더해주면된다.

 

q[T-1] 에서 가장 큰값을 출력해주면된다.