BOJ 2096 내려가기

www.acmicpc.net/problem/2096

2096번: 내려가기

슬라이딩 윈도를 사용해서 공간 복잡도를 O(1)로 만들고 풀어야 하는 문제.

라이님의 블로그를 참고해서 풀었다.

 

DP식 짜는 것은 매우 쉽지만 필요 메모리가 무려 4MB이다...

DP 식을 잘 보면

			cin >> TMX[j];
			TMN[j] = TMX[j];
			TMX[j] += max(MX[1], (j == 1) ? max(MX[0], MX[2]) : MX[j]);
			TMN[j] += min(MN[1], (j == 1) ? min(MN[0], MN[2]) : MN[j]);

3번, 4번째 줄은 DP 점화식을 갱신해주는 풀이이다.

		memcpy(MX, TMX, sizeof(int) * 3);
		memcpy(MN, TMN, sizeof(int) * 3);

이후 mx와 mn에 temp로 받은 배열들을 복사해주면 바로 그 윗 단계의 원소들로 문제를 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int MX[3], MN[3], TMX[3], TMN[3];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> TMX[j];
			TMN[j] = TMX[j];
			TMX[j] += max(MX[1], (j == 1) ? max(MX[0], MX[2]) : MX[j]);
			TMN[j] += min(MN[1], (j == 1) ? min(MN[0], MN[2]) : MN[j]);
		}
		memcpy(MX, TMX, sizeof(int) * 3);
		memcpy(MN, TMN, sizeof(int) * 3);
	}

	cout << *max_element(MX, MX + 3) << ' ' << *min_element(MN, MN + 3) << endl;

	return 0;
}

이런 슬라이딩 기법은 후에 최단 경로를 구하는 방법 중 하나인 폴라이드 알고리즘에서 사용된다고 한다..