SlidingWindow - 2096 - 내려가기.cpp

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

2096번: 내려가기

문제

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

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

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

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

출력

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

---

매번 한줄에 3개씩 값을 읽어오는데, 위치에 따라 영향 받는 값이 다른 점을 이용했다.

최댓값, 최솟값, 입력값, Temp 4개의 배열을 이용하여 구현한다.

A	B	C
D	E	F

예를 들어 위의 테이블과 같이 있을 때 최댓값을 구하는 상황을 가정해보자.

A, B, C는 이전까지 누적된 각각의 최댓값이다.

그리고 D, E, F는 방금 막 들어온 따끈한 입력값이다.

A는 D 혹은 E의 값으로 선택하여 내려갈 수 있고

B는 D, E, F 중 하나의 값을 선택하여 내려간다.

 

반대로 말하면 D는 A 혹은 B에 영향을 받고

E는 A, B, C 그리고 F는 B, C로부터 영향을 받는다.

다시 말하자면 D는 최댓값을 누적시키기 위해 A와 B중 더 큰 값을 택하여 더하고,

E는 A, B, C 중 더 가장 큰 값을 선택하여 누적시킨다.

F는 B, C 중 더 큰 값을 선택하여 누적시킨다.

Tmp[0] = max(Max[0], Max[1]) + In[0];
Tmp[1] = max(max(Max[0], Max[1]), Max[2]) + In[1];
Tmp[2] = max(Max[1], Max[2]) + In[2];

단 D, E, F가 이전의 Min 값을 이용할 수 있게 하기 위해

Tmp에 값을 임시로 저장한 후 D, E, F의 연산이 끝나면

Min 테이블의 값을 갱신시킨다.

Min[0] = Tmp[0];
Min[1] = Tmp[1];
Min[2] = Tmp[2];

n번 모두 실행 시킨 후 

Max[0], Max[1], Max[2] 중 가장 큰 값과 Min[0], Min[1], Min[2] 중 가장 작은 값을 출력한다.

#include<bits/stdc++.h>
#define X first
#define Y second
#define NUM 100002
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 987654321;
const int MOD = 10007;
const int MAX = 1000000000;
int Min[3], Max[3], In[3], Tmp[3];
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	cin >> In[0] >> In[1] >> In[2];
	Min[0] = Max[0] = In[0];
	Min[1] = Max[1] = In[1];
	Min[2] = Max[2] = In[2];
	for (int i = 1; i < n; i++) {
		cin >> In[0] >> In[1] >> In[2];
		Tmp[0] = min(Min[0], Min[1]) + In[0];
		Tmp[1] = min(min(Min[0], Min[1]), Min[2]) + In[1];
		Tmp[2] = min(Min[1], Min[2]) + In[2];
		Min[0] = Tmp[0];
		Min[1] = Tmp[1];
		Min[2] = Tmp[2];

		Tmp[0] = max(Max[0], Max[1]) + In[0];
		Tmp[1] = max(max(Max[0], Max[1]), Max[2]) + In[1];
		Tmp[2] = max(Max[1], Max[2]) + In[2];
		Max[0] = Tmp[0];
		Max[1] = Tmp[1];
		Max[2] = Tmp[2];
	}
	cout << max(max(Max[0], Max[1]), Max[2]) << ' ' << min(min(Min[0], Min[1]), Min[2]);
}