백준 1932(정수 삼각형) - python
2023. 10. 5. 19:09ㆍ알고리즘(python)/DP
접근
최대값을 구하는 문제. 배열을 만들어서 dp[i][j]일때의 최대값을 dp[i][j]에 저장하자. dp[i-1][j-1], dp[i-1][j]가 각각 해당자리의 최대값이라면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + cost[i][j] 가 된다. 해당 점화식을 보면 dp[i][j]를 구하기위해 dp[i-1] 만 필요하니 dp테이블을 모두 만드는것이아닌 1차원 2개만 만들면 메모리를 아낄 수 있다. 속도적인 측면에서는 그냥 배열을 쓰는게 좋겠지만 메모리를 절약하기 위해 1차원 배열 2개만을 이용해서 구현할 생각을 했다.
나의 코드
import sys
input = sys.stdin.readline
n = int(input())
dp = list(map(int,input().split()))
d = [-1 , 0]
for i in range(n-1):
cost = list(map(int,input().split()))
dp2 = []
for j , c in enumerate(cost):
maxv = 0
for k in d:
nextj = j + k
if 0 <= nextj <= i:
if maxv < dp[nextj]:
maxv = dp[nextj]
dp2.append(maxv+c)
dp = dp2
print(max(dp))
'알고리즘(python) > DP' 카테고리의 다른 글
백준 11053(가장 긴 증가하는 부분 수열) - python (0) | 2023.10.08 |
---|---|
백준9251(LCS) - python (0) | 2023.10.07 |
백준 1149(RGB) - python (1) | 2023.09.26 |