[BOJ/C++] 2096(내려가기)

Link: https://www.acmicpc.net/problem/2096

• max관련 변수랑 min관련 변수 복붙해서 처리하시는 분들은 만약 왜 틀리지 싶을 때 꼭 복붙한 변수 제대로 다 바꿔줬는지 확인하세요.(제 경우 대체 왜 틀렸는지 모르고 2시간 내리 로직 문제만 파악했거든요..)
• 메모리 문제 제한이 있으므로 단순 DP만으로 풀 수 없다는 점 또한 참고하면 좋습니다.

1. 세 개의 숫자 중에 시작, 최대 및 최소 점수를 구하여라 -> DP
2. 메모리 제한(4MB), N크기 >= 100,000 -> 단순 DP로 불가, 입력과 동시에 값을 변경해야겠다는 생각으로 슬라이딩 윈도우 예상

정답 코드

#include<iostream>
using namespace std;

int n;
int after[3], minDp[3]{ 0 }, maxDp[3]{ 0 };

int max(int a, int b) {
	if (a < b) return b;
	else return a;
}

int min(int a, int b) {
	if (a > b) return b;
	else return a;
}

void solution() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> after[j];
		}
		int maxTmp[3], minTmp[3];
		//[0]
		maxTmp[0] = max(maxDp[0], maxDp[1]) + after[0];
		minTmp[0] = min(minDp[0], minDp[1]) + after[0];
		//[1]
		maxTmp[1] = max(max(maxDp[0], maxDp[1]), maxDp[2]) + after[1];
		minTmp[1] = min(min(minDp[0], minDp[1]), minDp[2]) + after[1];
		//[2]
		maxTmp[2] = max(maxDp[1], maxDp[2]) + after[2];
		minTmp[2] = min(minDp[1], minDp[2]) + after[2];
		for (int j = 0; j < 3; ++j) {
			maxDp[j] = maxTmp[j];
			minDp[j] = minTmp[j];
		}
	}
	int maxAns = max(max(maxDp[0], maxDp[1]), maxDp[2]);
	int minAns = min(min(minDp[0], minDp[1]), minDp[2]);
	cout << maxAns << ' ' << minAns;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}