[BOJ]2096 : 내려가기(c++)

[문제] : https://www.acmicpc.net/problem/2096

[오답노트]

평범한(?) DP 문제라고 생각하고 cache를 [100001][3]정도 잡고 재귀로 풀었더니 메모리초과가 났다. 문제에 메모리 제한이 4 MB라서 메모이제이션에 쓰인 메모리를 더 줄여야만 했는데 아이디어가 떠오르지 않았다. 질문 게시판을 살펴보던중 이미 지나간 부분에 대한 정보는 필요없다라는 힌트를 얻었고 내가 구하고자 하는 현재 줄의 바로 아래 줄에 대한 정보만 있으면 되기 때문에(top-down의 경우) cache[2][3]만으로도 풀린다는 것을 알았다. 나는 보통 DP 문제를 탑다운으로 풀었기 때문에 이 문제 또한 탑다운으로 접근하였는데 어떤식으로 함수를 세워야 하는지 떠오르지 않아서 결국 다른 분 블로그를 참고해서 풀었다.

참고한 블로그 : https://jaehee-developer.tistory.com/53

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int map[100001][3];
int MaxDP[2][3];
int MinDP[2][3];
int dx[3] = { 1,1,1 };
int dy[3] = { -1, 0, 1 };
int N;
int main(void)
{
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			int a;
			cin >> a;
			map[i][j] = a;
		}
	}

	MaxDP[0][0] = MinDP[0][0] = map[N - 1][0];

	MaxDP[0][1] = MinDP[0][1] = map[N - 1][1];

	MaxDP[0][2] = MinDP[0][2] = map[N - 1][2];

	for (int i = N - 2; i >= 0; --i)
	{
			MaxDP[1][0] = map[i][0] + max(MaxDP[0][0], MaxDP[0][1]);
			MaxDP[1][1] = map[i][1] + max(MaxDP[0][0], max(MaxDP[0][1], MaxDP[0][2]));
			MaxDP[1][2] = map[i][2] + max(MaxDP[0][1], MaxDP[0][2]);

			MaxDP[0][0] = MaxDP[1][0];
			MaxDP[0][1] = MaxDP[1][1];
			MaxDP[0][2] = MaxDP[1][2];

			MinDP[1][0] = map[i][0] + min(MinDP[0][0], MinDP[0][1]);
			MinDP[1][1] = map[i][1] + min(MinDP[0][0], min(MinDP[0][1], MinDP[0][2]));
			MinDP[1][2] = map[i][2] + min(MinDP[0][1], MinDP[0][2]);

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



	cout << max(max(MaxDP[0][0], MaxDP[0][1]), MaxDP[0][2]) << " " 
		<< min(min(MinDP[0][0], MinDP[0][1]), MinDP[0][2]) << endl;
}

결국은 바텀업.. 탑다운으로 된 코드를 찾아보려 했는데 거의 다 바텀업이여서 포기했다(열심히 찾아보진 않았지만..) DP문제를 바텀업으로 풀었을 때 더 깔끔히 풀리는 문제들도 있고 바텀업으로만 풀리는 문제들도 있기 때문에 바텀업으로 푸는 연습을 좀 해야겠다.

언젠가 시간나면 이 문제도 탑다운으로..