[백준]내려가기2096 C++

문제 링크

생각해야할 부분

1. 메모리 제한이 4MB이다.
   보통 문제 풀때 시간 제한만 보고 알고리즘을 구상하다보니 첫 제출에서 메모리 초과가 났다. ㅜ.ㅜ
   dp 문제라 메모라이즈하려는 생각에 간과한 메모리초과라고 할 수 있다.
   첫 풀이에서는 vector을 써서 n만큼 입력 벡터와 dp 벡터를 할당해 주었다. 사실 이도 십만 x 3 x 2 x 4바이트(int)라 얼추 가능할거라 생각했다.
   But c++ 자체에서 1-2MB 사용하고 iostream 사용시 기본 2MB 사용한다고 한다.. 그러면 절대 안되지..
   알고나면 간단한 문제이고 더 좋은 코드를 쓰기 위해 중요한 부분인거 같다.

정답 풀이

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

pair<int, int> dp[3][3];
int n;
void getValue(int []);
int main() {
	cin >> n;
	int arr[3];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int temp;
			cin >> temp;
			arr[j] = temp;
		}
		if (i == 0) {
			dp[0][0]=make_pair(arr[0], arr[0]);
			dp[0][1]=make_pair(arr[1], arr[1]);
			dp[0][2]=make_pair(arr[2], arr[2]);
		}else getValue(arr);
	}
	cout << max({ dp[0][0].second, dp[0][1].second, dp[0][2].second }) << " " << min({ dp[0][0].first, dp[0][1].first, dp[0][2].first });
	return 0;
}
void getValue(int a[]) {
	//order번째 인덱스 체크중
	int minV;
	int maxV;

	//case 0: //0 or 1갈 수 있다.
	minV= min(dp[0][0].first, dp[0][1].first)+a[0];
	maxV= max(dp[0][0].second, dp[0][1].second)+a[0];
	dp[1][0]=make_pair(minV, maxV);
	//case 1: //0 or 1 or 2갈 수 있다.
	minV = min({ dp[0][0].first, dp[0][1].first ,dp[0][2].first})+a[1];
	maxV= max({ dp[0][0].second, dp[0][1].second ,dp[0][2].second })+a[1];
	dp[1][1]=make_pair(minV, maxV);
	//case 2: //1 or 2갈 수 있다.
	minV= min(dp[0][1].first, dp[0][2].first)+a[2];
	maxV= max(dp[0][1].second, dp[0][2].second)+a[2];
	dp[1][2]=make_pair(minV, maxV);
	swap(dp[0], dp[1]);
}
/*
n= 십만
dp[n번째 줄][i번째 칸]=[최소,최대]=dp[n-1][가능한 i중] <min,max>
메모리 제한이 4MB로 그냥 n으로 만들어서 구현하면 초과가 난다.

*/