Baekjoon 2096 내려가기

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

결과 3160KB / 24ms

언어 C++17

 

풀이

문제 조건이 너무 명확하다

못가는 위치를 제외한 합의 최대값을 현개 값으로 잡으면된다.

다만 메모리제한이 4MB인 점을 생각해

모든 위치를 기억하는것이 아닌 현재와 이전 1개의 라인만 기억하는 배열을 만들면 된다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 100000;

int input[MAX][3] = {};

int maxBuffer[2][3] = {};
int minBuffer[2][3] = {};

int _max(const int a, const int b) { return a ^ ((a ^ b) & -(a < b)); }
int _min(const int a, const int b) { return b ^ ((a ^ b) & -(a < b)); }

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

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++)
			cin >> input[i][j];
	}

	for (int i = 0; i < 3; i++) {
		maxBuffer[0][i] = minBuffer[0][i] = input[0][i];
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			int res = 0;
			switch (j) {
			case 0:
				minBuffer[1][j] = input[i][j] + _min(minBuffer[0][0], minBuffer[0][1]);
				maxBuffer[1][j] = input[i][j] + _max(maxBuffer[0][0], maxBuffer[0][1]);
				break;
			case 1:
				minBuffer[1][j] = input[i][j] + _min(_min(minBuffer[0][0], minBuffer[0][1]), minBuffer[0][2]);
				maxBuffer[1][j] = input[i][j] + _max(_max(maxBuffer[0][0], maxBuffer[0][1]), maxBuffer[0][2]);
				break;
			case 2:
				minBuffer[1][j] = input[i][j] + _min(minBuffer[0][1], minBuffer[0][2]);
				maxBuffer[1][j] = input[i][j] + _max(maxBuffer[0][1], maxBuffer[0][2]);
				break;
			}
		}

		for (int j = 0; j < 3; j++) {
			minBuffer[0][j] = minBuffer[1][j];
			maxBuffer[0][j] = maxBuffer[1][j];
		}
	}

	cout << _max(_max(maxBuffer[0][0], maxBuffer[0][1]), maxBuffer[0][2]) << ' ' << _min(_min(minBuffer[0][0], minBuffer[0][1]), minBuffer[0][2]);


	return 0;
}