[baekjoon] 백준 2096번 : 내려가기 (by python 파이썬) 다이나믹프로그래밍 dp

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

2096번: 내려가기

 

정답 code

#내려가기
import sys
input = sys.stdin.readline

n = int(input())
score = list(map(int,input().split()))
maxdp = score
mindp = score

for _ in range(n-1):
    a,b,c = map(int,input().split())
    maxdp = [a+max(maxdp[0], maxdp[1]), b+max(maxdp), c+max(maxdp[1],maxdp[2])]

    mindp = [a+min(mindp[0], mindp[1]), b+min(mindp), c+min(mindp[1],mindp[2])]

print(max(maxdp) ,min(mindp))

 

solution

문제에서 원하는 조건을보고 다이나믹프로그래밍을 이용해 해결해야 겠다고 생각이 들었다.

처음에는 모든 입력값을 받아둔 배열을 만든 상태에서 순차적으로 돌아가면서 max값과 min값을 구해주었다.

 

하지만! 메모리제한이 있었다. (4mb) 

구글링을 해본 결과 슬라이딩 윈도우라는 기법을 사용해야했다.

 

한줄씩 입력을 받고,

더 이상 필요하지 않는 값을 없애며  최대 최소에 따라 계속 3자리의 배열값을 갱신해준다. 

 

제일 왼쪽값은 위와 오른쪽위, 중앙값은 위의줄 전부, 오른쪽값은 위와 왼쪽위의 값중 최대,최소를 구해 갱신해주면 된다.

 

아래 블로그 참고

https://my-coding-notes.tistory.com/318

[🥇4 / 백준 2096 / 파이썬] 내려가기