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

문제 링크: www.acmicpc.net/problem/2096

2096번: 내려가기

1.주의할 점

- 메모리의 제한이 극단적이니 배열의 크기를 최소로 한다

 

2. 구현

- 각 줄을 Arr[]배열에 입력받는다

- 만약 첫 번째 줄이라면, Maxi[1][], Mini[1][] 배열에 그대로 값을 대입한다. Maxi[0][] 배열은 t번째 숫자를 입력받기전인 t-1번까지의 최대 점수를 저장하는 배열이다. Maxi[1][] 배열은 t번째 숫자를 받은 후, t번째까지의 최대 점수를 저장하는 배열이다. Mini[][]의 경우, Maxi[][]배열과 동일하나, 최대 점수가 아닌 최소 점수를 저장한다

- 게임의 제약조건을 점화식으로 풀어낸다

 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[3];
int maxi[2][3], mini[2][3];		//[0][]: pre, [1][]: cur
int num;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> num;
	for (int t = 0; t < num; t++) {
		for (int i = 0; i < 3; i++)
			cin >> arr[i];
		if (t == 0) {
			for (int i = 0; i < 3; i++)
				maxi[1][i] = mini[1][i] = arr[i];
		}
		else {
			maxi[1][0] = max(maxi[0][0], maxi[0][1]) + arr[0];
			maxi[1][1] = max(max(maxi[0][0], maxi[0][1]), maxi[0][2]) + arr[1];
			maxi[1][2] = max(maxi[0][2], maxi[0][1]) + arr[2];

			mini[1][0] = min(mini[0][0], mini[0][1]) + arr[0];
			mini[1][1] = min(min(mini[0][0], mini[0][1]), mini[0][2]) + arr[1];
			mini[1][2] = min(mini[0][2], mini[0][1]) + arr[2];
		}
		for (int i = 0; i < 3; i++) {
			maxi[0][i] = maxi[1][i];
			mini[0][i] = mini[1][i];
		}
	}
	int maxR = max(max(maxi[0][0], maxi[0][1]), maxi[0][2]);
	int minR = min(min(mini[0][0], mini[0][1]), mini[0][2]);
	cout << maxR << " " << minR;
	return 0;
}