일반적인 DP문제로 해결하면 메모리 초과 문제가 발생한다. 그 이유는 다른 문제와 다르게 메모리 제한이 4MB로 아주 작게 설정돼있다. 그렇기 때문에 기존 방식처럼 배열을 많이 만들어놓고 한 인덱스씩 채워 나가는 형태로 문제를 해결한다면 메모리 초과 문제가 발생한다.

실패 코드

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;
int n;
//이렇게 빈공간을 할애할시 문제의 4MB 용량을 뛰어넘게됨
int coa[1000001][3] = { 0 };
int ary[100001][3] = { -1 };

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

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

	for (int i = 1; i <= n; i++) {
		coa[i][0] = ary[i][0] + max(coa[i - 1][0], coa[i - 2][1]);
		coa[i][1] = ary[i][1] + max(coa[i - 1][0], max(coa[i - 1][2], coa[i - 1][1]));
		coa[i][2] = ary[i][2] + max(coa[i - 1][1], coa[i - 1][2]);
	}

	cout << max(coa[n][0], max(coa[n][1], coa[n][2])) << " ";

	for (int i = 1; i <= n; i++) {
		coa[i][0] = ary[i][0] + min(coa[i-1][0], coa[i-2][1]);
		coa[i][1] = ary[i][1] + min(coa[i-1][0], min(coa[i-1][2], coa[i-1][1]));
		coa[i][2] = ary[i][2] + min(coa[i-1][1], coa[i-1][2]);
	}

	cout << min(coa[n][0], min(coa[n][1], coa[n][2]));

	return 0;

}

단독으로 갱신하고 적용하는 방식으로 구현해야 한다.

성공 코드

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;
int n;
//이렇게 빈공간을 할애할시 문제의 4MB 용량을 뛰어넘게됨
int mx[3] = { 0 };
int mi[3] = { 0 };
int x, y, z;

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

	cin >> n;
	cin >> x >> y >> z;

	mx[0] = x;
	mx[1] = y;
	mx[2] = z;

	mi[0] = x;
	mi[1] = y;
	mi[2] = z;

	for (int i = 1; i < n; i++) {
		int q, w, e;
		x, y, z = 0;
		cin >> x >> y >> z;

		q = mx[0];
		w = mx[1];
		e = mx[2];

		mx[0] = max(q, w) + x;
		mx[1] = max(q, max(w,e)) + y;
		mx[2] = max(w, e) + z;

		q = mi[0];
		w = mi[1];
		e = mi[2];

		mi[0] = min(q, w) + x;
		mi[1] = min(q, min(w, e)) + y;
		mi[2] = min(w, e) + z;
		
	}

	cout << max(mx[0], max(mx[1], mx[2])) << " " << min(mi[0], min(mi[1], mi[2]));

	return 0;

}