[BOJ]2096번: 내려가기

 

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

---

슬라이딩 윈도우 문제입니다. 메모리 제한이 심상치 않습니다.

 

발판은 board[N][3]의 형태를 가지고 있지만,

i번째 칸을 계산함에 있어서 필요한 발판정보는 i-1번째 칸의 정보만 필요합니다.

그러므로 메모이제이션을 위한 dp[][] 배열이나 input값을 저장하는 board[][] 배열 모두 [2][3] 크기면 됩니다.

 

dp배열을 다음과 같이 정의내리겠습니다.

 

max_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최댓값

min_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최솟값 

 

끝으로 dp[i][], dp[i+1][] 이렇게 두 칸만 사용하기 위해 % 2 연산을 사용했습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2096.cc