회전초밥

항상 이런 DP문제들을 보면 어떤 값을 배열의 index로 표현할까가 나의 관심사였다. 가장 배열에 넣을 만한 값들은 예산에 해당하는 값들이었고 이 값들이 배열의 최대 범위를 초과하지 않기를 기도할 뿐이었다.

하지만 최대 범위를 초과한다면.. 그 문제는 내겐 그때부터는 DP문제가 아니였다. 어떻게 최적화 할 것인가 머리를 짜매다가 풀지 못한 문제로 남아버렸다.

책에서본 회전초밥문제도 그랬다. 단순 DP문제로 풀 수 있을 줄 알았는데 예산의 범위가 10^9이하여서 배열로 넣기는 무리였다. 문제의 힌트로 가격이 항상 100의 배수라 10^7정도는 배열에 넣으면 되겠다 생각했는데 메모리의 크기 제한이 64MB였다.

int형으로 배열의 크기가 10^7로 잡자니 메모리가 초과할 것 같고 그렇다고 최대한 메모리를 쪼개고 쪼개 char형으로 배열을 선언하지나 답의 범위를 온전히 표현하지 못할 것 같았다.

이런 경우에 사용하는 방법이 슬라이딩 윈도우이다. 슬라이딩 윈도우란 사용하는 데이터 전체를 메모리에 유지하는 것이 아니라 필요한 것들만 저장해두는 방식이다. 가장 대표적인예로는 피보나치배열의 n번째 항을 구하는 방법이다.

 
int fibo(int n) {
	if (n <= 1) return n;
	int seq[3];
	seq[0] = 0;
	seq[1] = 1;
	for (int i = 2; i <= n; i++)
		seq[i % 3] = seq[(i - 1) % 3] + seq[(i - 2) % 3];
}

하나의 피보나치 항을 업데이트하는데 필요한 값은 총 3개이고 이때 사용하는 메모리들은 모두 재활용 될 수 있기에 크기 3인 배열로 해결 할 수 있다.

위 기법을 초밥문제 풀 때도 사용해볼 수 있었다.

c[현재 체크중인 예산 - 초밥의 최대 가격]이전의 값들은 필요가 없다. 배열의 값이 업데이트하면서 예전에 사용했던 값들은 쓸모가 없어진다. 이런 경우에 모든 최적화 경우의 값들을 초밥의 최대 가격 안에서 표현이 가능해진다. 즉 초밥의 최대 가격 만큼 배열의 크기를 선언해줄 수 있다.

 
int solve(int c, int n) {
	int budget, i;
	int ret = 0;

	for (budget = 0; budget <= c; budget++) {
		int cand = 0;
		for (i = 0; i < n; i++) {
			if (budget >= price[i])
				cand = max(cand, cost[(budget - price[i]) % 201] + pref[i]);
			cost[budget % 201] = cand;
			ret = max(ret, cand);
		}
	}

	return ret;
}

cost[(budget-price[i])%201] 은 budget - price 예산에서 최대 높은 선호도를 갖는 값이다. 모듈러 연산을 통해 이전의 필요없는 값들을 제거한 것에 주목할 필요가 있다.

역시 고수들은 다르다. 책에서 많은걸 배우는것 같다