2096번 내려가기

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int max_arr[2][3];
int min_arr[2][3];

void solve() {
	int N;
	int a, b, c;
	int k = 0;
	cin >> N;
	int flag1 = 2, flag2 = 2;
	for (int i = 0; i < N; i++)
	{
		cin >> a >> b >> c;
		
		max_arr[k][0] = max(max_arr[1 - k][0], max_arr[1 - k][1]) + a;
		max_arr[k][1] = max(max_arr[1 - k][0], max(max_arr[1 - k][1],max_arr[1-k][2])) + b;
		max_arr[k][2] = max(max_arr[1 - k][1], max_arr[1 - k][2]) + c;

		min_arr[k][0] = min(min_arr[1 - k][0], min_arr[1 - k][1]) + a;
		min_arr[k][1] = min(min_arr[1 - k][0], min(min_arr[1 - k][1], min_arr[1 - k][2])) + b;
		min_arr[k][2] = min(min_arr[1 - k][1], min_arr[1 - k][2]) + c;

		k = 1 - k;
	}

	int maxNum = max(max_arr[1 - k][0], max(max_arr[1 - k][1], max_arr[1 - k][2]));
	int minNum = min(min_arr[1 - k][0], min(min_arr[1 - k][1], min_arr[1 - k][2]));

	cout << maxNum << ' ' << minNum;
}

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

	solve();
	return 0;
}

풀이

메모리 제한이 심하게 걸려있는 문제이다. 입력되는 때마다 동적으로 확인하며 연산해야한다. 슬라이딩 윈도우 이용

입력된 값을 저장하기위한 행과 연산 결과를 저장할 행이 필요하다. 또한, 최대값과 최소값을 따로 구해야하기 때문에 2x3배열을 두개 준비한다.
최대값을 구해야하는 배열에서는 최대값을 구하며 내려가고 최소값을 구해야하는 배열에서는 최소값을 구하며 내려간다.

현재 입력된 행과 이전에 입력된 행의 역할이 번갈아가며 진행된다. 이전에 입력된 행의 값들을 현재 입력된 행에 연산해주고 다음 입력때는 이전에 입력된 행에 입력을 해주는 형식으로 진행한다.