[백준]2096_내려가기

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

Solved

✔ DP, 슬라이딩 윈도우
✔ 슬라이딩 윈도우
투포인터 알고리즘으로, 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다.
예를 들어 정수로 이루어진 다음의 배열에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은 무엇인가? 같은 문제에서 사용될 수 있다.

단순한 방식으로 서브 배열의 요소를 순회하다 보면 중복되는 요소들이 존재한다.

중복되는 요소들을 재사용하는 방법이 슬라이딩 윈도우 알고리즘의 핵심이다.

투포인터 알고리즘은 left와 right라는 처음과 끝을 가리키는 포인터과 서로 독립적으로 움직이는 데에 반해, 슬라이딩 윈도우 알고리즘은 처음과 끝을 가리키는 포인터과 서로 같이 움직인다.

처음과 끝에 대해서 삽입과 삭제가 빈번히 이뤄지기 때문에 deque 구조가 보통 사용된다.

using namespace std;
#include <iostream>
#include <cstring>
#define MAX 100000

int n;
int dp_max[3], dp_min[3], cur[3];

int main() {
	cin >> n;
	int a, b, c;
	cin >> dp_max[0] >> dp_max[1] >> dp_max[2];
	memcpy(dp_min, dp_max, sizeof(dp_min));
	for (int i = 1; i < n; i++) {
		cin >> cur[0] >> cur[1] >> cur[2];
		int t0 = dp_max[0], t1 = dp_max[1], t2 = dp_max[2];
		dp_max[0] = max(t0, t1) + cur[0];
		dp_max[1] = max(t0, max(t1, t2)) + cur[1];
		dp_max[2] = max(t1, t2) + cur[2];
		t0 = dp_min[0]; t1 = dp_min[1]; t2 = dp_min[2];
		dp_min[0] = min(t0, t1) + cur[0];
		dp_min[1] = min(t0, min(t1, t2)) + cur[1];
		dp_min[2] = min(t1, t2) + cur[2];
	}
	int ans_max = max(dp_max[0], max(dp_max[1], dp_max[2]));
	int ans_min = min(dp_min[0], min(dp_min[1], dp_min[2]));

	cout << ans_max << ' ' << ans_min << '\n';
	return 0;
}