[백준 BOJ 2096 gold4 - 내려가기] sliding window, dynamic programming

 

백준 내려가기 gold 4

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

2096번: 내려가기

 

 

N*3 배열이 주어지고, 위에서부터 인접한 위치로 내려가며, 최댓값과 최솟값을 출력하는 문제이다.

평범한 dp로 풀면 될 것 같다.

 

그런데.. 메모리 제한이 4MB이다.

즉, 일반적으로 생각하는 dp배열을 만들어서 푸는 풀이는 메모리 초과가 나게 된다.

 

sliding window기법을 사용한다. 전체 배열 크기만큼 dp배열을 만드는 게 아니라 실질적으로 필요한 데이터만 저장할 수 있게 배열을 선언해보자.

 

이 경우, 현재 입력되는 3개의 수와 , 이전 row의 3수를 알면 최대와 최소를 계산할 수 있으므로 2*3 크기의 배열만 있어도 된다.

 

		int row = i % 2;
		wmin[row][0] = min(wmin[1 - row][0] + a, wmin[1 - row][1] + a);
		wmin[row][1] = min({ wmin[1 - row][0] + b ,wmin[1 - row][1] + b , wmin[1 - row][2] + b });
		wmin[row][2] = min(wmin[1 - row][1] + c, wmin[1 - row][2] + c);
	
		wmax[row][0] = max(wmax[1 - row][0] + a, wmax[1 - row][1] + a);
		wmax[row][1] = max({ wmax[1 - row][0] + b ,wmax[1 - row][1] + b , wmax[1 - row][2] + b });
		wmax[row][2] = max(wmax[1 - row][1] + c, wmax[1 - row][2] + c);

최대와 최소 배열을 두개 선언하여 지금 입력 받은 수(a,b,c) 와 그전 3개의 수로 최대 최소를 계산하여 해결하였다