[백준 2096 | C++] 내려가기 :: 다이나믹 프로그래밍(DP)

• 문제 링크 : 2096번: 내려가기
• 관련 태그 : 다이나믹 프로그래밍, 슬라이딩 윈도우
• 참고 문제 : 1149번: RGB거리
  
  • 소스 코드: http://boj.kr/2c560b76c1d0407d9606b73e2e96e212

 

풀이

RGB거리와 거의 유사한 문제입니다. 

다만 이 문제는 메모리 제한이 4MB로 제한이 있습니다. 이 경우, 입력 테이블과 DP 테이블을 n행짜리를 만들면 무조건 시간초과가 납니다. 

따라서 토글링 기법을 사용하여 메모리를 절약할 수 있습니다. 

 

토글링 기법이란?

DP에서 토글링 기법은 메모리 최적화를 위해 사용된다. 일반적으로 DP는 2차원의 배열을 사용하여 각 단계의 값을 저장한다. 그러나 토글링 기법은 현재 상태와 이전 상태만을 유지하여 메모리 사용량을 줄인다.

DP[1]의 값을 생성하고 바로 DP[0]에 대입하면 안되는 이유

: 예를 들어 DP[1][1]의 값을 생성할 때 DP[0][0]의 값이 필요한 경우가 있다. 이때 DP[0][0]의 값을 업데이트해버리면 의도치 않은 결과가 나올 수 있다.

---

단순히 DP 테이블을 만든 경우 : 시간초과

// 메모리 초과 : 틀린 코드입니다
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<vector<int>>v(n, vector <int>(3, 0));
	vector<vector<int>>min_dp(n, vector <int>(3, 0));
	vector<vector<int>>max_dp(n, vector <int>(3, 0));

	for (int i = 0; i < n;i++) {
		cin >> v[i][0] >> v[i][1] >> v[i][2];
	}


	int tmp = 0;
	// 최대 점수
	max_dp[0][0] = v[0][0]; max_dp[0][1] = v[0][1]; max_dp[0][2] = v[0][2];
	for (int i = 1; i < n;i++) {
		// 0열
		max_dp[i][0] = max(max_dp[i - 1][0], max_dp[i - 1][1]) + v[i][0];

		// 1열
		tmp = max(max_dp[i - 1][0], max_dp[i - 1][1]);
		max_dp[i][1] = max(tmp, max_dp[i - 1][2]) + v[i][1];

		// 2열
		max_dp[i][2] = max(max_dp[i - 1][1], max_dp[i - 1][2]) + v[i][2];
	}

	tmp = max(max_dp[n - 1][0], max_dp[n - 1][1]);
	cout << max(tmp, max_dp[n - 1][2]) << ' ';	


	// 최소 점수
	min_dp[0][0] = v[0][0]; min_dp[0][1] = v[0][1]; min_dp[0][2] = v[0][2];
	for (int i = 1; i < n;i++) {
		// 0열
		min_dp[i][0] = min(min_dp[i - 1][0], min_dp[i - 1][1]) + v[i][0];

		// 1열
		tmp = min(min_dp[i - 1][0], min_dp[i - 1][1]);
		min_dp[i][1] = min(tmp, min_dp[i - 1][2]) + v[i][1];

		// 2열
		min_dp[i][2] = min(min_dp[i - 1][1], min_dp[i - 1][2]) + v[i][2];
	}

	tmp = min(min_dp[n - 1][0], min_dp[n - 1][1]);
	cout << min(tmp, min_dp[n - 1][2]);
}

• 입력 벡터 v : n행 3열
• 최소 점수를 구하는 min_dp : n행 3열
• 최대 점수를 구하는 max_dp : n행 3열

 

토글링 기법을 활용하여 메모리 최적화 : 맞았습니다! 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<vector<int>>v(1, vector <int>(3, 0));
	vector<vector<int>>min_dp(2, vector <int>(3, 0));
	vector<vector<int>>max_dp(2, vector <int>(3, 0));

	// i = 0 일때
	cin >> v[0][0] >> v[0][1] >> v[0][2];

	max_dp[0][0] = v[0][0]; max_dp[0][1] = v[0][1]; max_dp[0][2] = v[0][2];
	min_dp[0][0] = v[0][0]; min_dp[0][1] = v[0][1]; min_dp[0][2] = v[0][2];

	int tmp = 0;
	for (int i = 1; i < n;i++) {
		cin >> v[0][0] >> v[0][1] >> v[0][2];

		// 최대 점수
		// 0열
		max_dp[1][0] = max(max_dp[0][0], max_dp[0][1]) + v[0][0];

		// 1열
		tmp = max(max_dp[0][0], max_dp[0][1]);
		max_dp[1][1] = max(tmp, max_dp[0][2]) + v[0][1];

		// 2열
		max_dp[1][2] = max(max_dp[0][1], max_dp[0][2]) + v[0][2];

		max_dp[0][0] = max_dp[1][0]; max_dp[0][1] = max_dp[1][1]; max_dp[0][2] = max_dp[1][2];
		max_dp[1][0] = 0; max_dp[1][1] = 0; max_dp[1][2] = 0;

		// 최소 점수
		// 0열
		min_dp[1][0] = min(min_dp[0][0], min_dp[0][1]) + v[0][0];

		// 1열
		tmp = min(min_dp[0][0], min_dp[0][1]);
		min_dp[1][1] = min(tmp, min_dp[0][2]) + v[0][1];

		// 2열
		min_dp[1][2] = min(min_dp[0][1], min_dp[0][2]) + v[0][2];

		min_dp[0][0] = min_dp[1][0]; min_dp[0][1] = min_dp[1][1]; min_dp[0][2] = min_dp[1][2];
		min_dp[1][0] = 0; min_dp[1][1] = 0; min_dp[1][2] = 0;
	}

	tmp = max(max_dp[0][0], max_dp[0][1]);
	cout << max(tmp, max_dp[0][2]) << ' ';	

	tmp = min(min_dp[0][0], min_dp[0][1]);
	cout << min(tmp, min_dp[0][2]);
}

• 입력이 한 줄 씩 들어올 때 마다 dp테이블 업데이트 → 입력 벡터 v : 1행 3열
• min_dp, max_dp : 2행 3열