BOJ 2096 - 내려가기

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

문제

어떤 칸을 선택하면 선택 가능한 다음 칸이 정해지는 점에서 9465번 - 스티커와 굉장히 유사합니다. 사실 동일한 풀이로 해결되지만 다른 점이 있습니다.

이 문제는 메모리의 제한이 4MB로 엄청 작다는 겁니다.

적은 메모리 제한때문에 스티커 문제처럼 dp[3][N] 과 같은 배열을 선언할 수도 없고 재귀 함수까지도 염려해야하는 상황입니다. 그럼 어떻게 해결해야할까요?

풀이

어떤 r번째 줄에서 어떤 칸을 선택한다면, 이는 다음 줄인 r+1번째 줄에 영향이 갑니다. 

어떤 칸을 선택할 때, 항상 2개의 줄만 확인하면 된다는 점으로 메모리를 줄일 수 있습니다.
왜냐하면 1번째 줄은 2번째 줄에 영향을 주고 2번째 줄은 3번째 줄에 영향을 주지만, 이미 이 시점에서 1번째 줄에서 선택한 결과들은 2번째 줄에 포함되어 있기 때문입니다.

이런 점을 활용한다면 배열의 크기를 dp[N][3] 에서 dp[2][3] 으로 줄일 수 있습니다. 마치 좌->우, 우->좌가 반복되는 형식처럼 생각하시면 편합니다.

코드