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

문제 : www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

풀이

바로 너비우선탐색으로 풀다 바꿔 풀었다.

dp에 해당 위치까지의 최대값을 저장한다.

a에 왼쪽 위를 더한값과 오른쪽 위를 더한값을 추가하여 둘중 최대값을 해당 위치 값으로 저장한다.

왼쪽 위와 오른쪽 위를 더할 때 범위가 벗어나지 않도록 조건문을 걸어준다.

 

n = int(input())
A = []
for i in range(n):
    temp = list(map(int, input().split(" ")))
    A.append(temp)

dp = []
for i in range(1,n+1):
    temp = [0 for _ in range(i)]
    dp.append(temp)

dp[0][0] = A[0][0]

for i in range(1,n):
    for j in range(i+1):
        a = []
        if j < i:
            a.append(dp[i-1][j]+A[i][j])
        if j-1>=0:
            a.append(dp[i-1][j-1]+A[i][j])
        dp[i][j] = max(a)

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