[백준] 내려가기 2096번 (python) 원도우를 활용한 DP

출처 : https://www.acmicpc.net/problem/2096

풀이 방법

처음에는 일반적인 DP문제로 풀이하였다 max와 min은 함수만 다르게 사용하고 점화식은 똑같다.

처음 풀이 방법

dp[i][j] = i, j일 때 최대 포인트 ( 0 <= j <= 3)

dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + point[i][0]

dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2])) + point[i][1]

dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + point[i][2]

최소일 때는 반대 

이렇게 max일 때와 min일 때 반복문을 두 번 돌았다.

이렇게 풀이하게 된다면 메모리 초과가 발생하게 된다.

 

그래서 윈도우를 활용해야하는데 윈도우를 사용하는 방법은 사용하지 않는 dp를 저장하지 않는 것이다.

즉 i번째 dp의 값을 구하려면 i-1번째 dp의 값만 필요하므로 i-1번째 dp의 값만 저장한다.

그렇게 한다면 점화식이 아래와 같다.

maxDp = [max(maxDp[0], maxDp[1]) + point[0], max(maxDp[0], max(maxDp[1], maxDp[2])) + point[1], max(maxDp[1], maxDp[2]) + point[2]]

min일 때는 max함수를 min으로 수정해 주면 된다.

 

전체 코드

N = int(input())

point = list(map(int, input().split()))
maxDp = point
minDp = point

for i in range(N-1):
    point = list(map(int, input().split()))
    maxDp = [max(maxDp[0], maxDp[1]) + point[0], max(maxDp[0], max(maxDp[1], maxDp[2])) + point[1], max(maxDp[1], maxDp[2]) + point[2]]
    minDp = [min(minDp[0], minDp[1]) + point[0], min(minDp[0], min(minDp[1], minDp[2])) + point[1], min(minDp[1], minDp[2]) + point[2]]

print(max(maxDp), min(minDp))