백준 2096번 내려가기 C++

출처 : https://www.acmicpc.net/problem/2096

 

최대 점수 : dp[i][j] = 붙어있는 dp[i-1]중 MAX + v[i][j]

최대 점수 : dp[i][j] = 붙어있는 dp[i-1]중 MIN+ v[i][j] 

인데, 메모리 제한이 4MB 이기 때문에 2차원 배열을 만들지 않고 입력받는대로 값을 갱신하면서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

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

	int n;
	cin >> n;
	int score[3];
	int dp_Max[3];
	int dp_Min[3];

	for (int i = 0; i < 3; i++) {
		int input;
		cin >> input;
		dp_Max[i] = input;
		dp_Min[i] = input;
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> score[j];
		}
		int lastMax0 = dp_Max[0];
		int lastMax1 = dp_Max[1];
		int lastMax2 = dp_Max[2];
		dp_Max[0] = max(lastMax0, lastMax1) + score[0];
		dp_Max[1] = max(max(lastMax0, lastMax1), lastMax2) + score[1];
		dp_Max[2] = max(lastMax1, lastMax2) + score[2];

		int lastMin0 = dp_Min[0];
		int lastMin1 = dp_Min[1];
		int lastMin2 = dp_Min[2];
		dp_Min[0] = min(lastMin0, lastMin1) + score[0];
		dp_Min[1] = min(min(lastMin0, lastMin1), lastMin2) + score[1];
		dp_Min[2] = min(lastMin1, lastMin2) + score[2];
	}

	int ansMax = max(max(dp_Max[0], dp_Max[1]), dp_Max[2]);
	int ansMin = min(min(dp_Min[0], dp_Min[1]), dp_Min[2]);
	cout << ansMax << " " << ansMin;
};