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

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

 

 

 

[풀이]

처음에는 완전탐색 기반의 DFS로 풀었다.

하지만 정수 삼각형이 500 depth까지 들어가다 보니 중복 연산으로 인해 시간초과가 되었다.

 

이것을 해결하기 위해 DP 개념을 활용하였다.

DP는 이미 진행한 연산에 대해 저장해두고, 기존 연산 결과를 다시 활용하는 기법이다.

 

예를 들어 1-2-1-1 이라는 경로와, 1-2-2-1 이라는 경로를 지나갈 때

1-2 경로에 대해서는 해당 누적된 값에 대해 최댓값을 미리 구했다면, 여러 번 연산 할 필요 없이 기존 연산 결과를 활용하면 된다.

 

때문에, DP 테이블을 별도로 만들어 두어 기존 경로를 지나온 것에 대한 누적된 연산 결과를 그대로 활용할 수 있도록 코드를 변경하였다.

 

 

 

[코드]

n = int(input())
ns = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1e9] * n for _ in range(n)]

dp[0][0] = ns[0][0]
for i in range(n - 1):
    for j in range(i + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + ns[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + ns[i + 1][j + 1])

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

 

 

 

[시간복잡도]

O(N^2)