[BOJ] 2096번_내려가기_슬라이딩 윈도우 (C++)

[문제]

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

N개의 줄에 0이상 9이하의 숫자가 세 개씩 적혀 있는 숫자판이 존재한다. 첫 줄에서 시작해서 마지막 줄까지 아래의 규칙을 따라 내려갈 때, 얻을 수 있는 최대 점수와 최소 점수를 구하는 프로그램을 작성하는 문제이다.

• 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작한다.
• 다음 줄로 내려갈 때에는 바로 아래의 수로 넘어가거나, 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다.
• 방문한 칸에 적혀있는 숫자의 합이 총 점수이다.

[사용 알고리즘]

슬라이딩 윈도우

[풀이 핵심]

• 처음에는 일반적인 dp문제라 생각해서 dp[100000][3] 배열을 만들어서 해결하려고 했으나 메모리 제한이 4MB이기 때문에 메모리 초과가 난다는 것을 깨달았다.
• 해당 문제는 현재 줄과 바로 이전 줄만 있으면 풀 수 있기 때문에 슬라이딩 윈도우 알고리즘을 통해 해결할 수 있다. 슬라이딩 윈도우란, 고정된 크기의 윈도우(배열)이 이동하며 윈도우 안에 있는 데이터 값으로 문제를 해결하는 방법이다.
• 현재줄의 0번 칸은 이전줄의 0번, 1번 칸에서 올 수 있고, 현재줄의 1번칸은 이전줄의 0번, 1번, 2번칸에서 올 수 있다. 마지막으로 현재줄의 2번 칸은 이전 줄의 1번, 2번칸에서 올 수 있다. 이점을 통해 현재줄의 0번, 1번, 2번 칸까지 도달하는데 최대 점수, 최소 점수를 구할 수 있다. 그렇게 마지막 줄까지 구하면 최대 점수, 최소점수를 알 수 있다.

[코드]

//boj2096번_내려가기_슬라이딩 윈도우

#include<iostream>

using namespace std;

int dp_max[3];
int dp_min[3];

int main() {
	int N;
	cin >> N;

	for (int i = 0; i < 3; i++) {
		int num;
		cin >> num;

		dp_max[i] = num;
		dp_min[i] = num;
	}

	for (int i = 1; i < N; i++) {
		int num0, num1, num2;
		cin >> num0 >> num1 >> num2;

		int max0 = dp_max[0], max1 = dp_max[1], max2 = dp_max[2];
		int min0 = dp_min[0], min1 = dp_min[1], min2 = dp_min[2];


		dp_max[0] = num0 + max(max0, max1);
		dp_max[1] = num1 + max(max(max0, max1), max2);
		dp_max[2] = num2 + max(max1, max2);

		dp_min[0] = num0 + min(min0, min1);
		dp_min[1] = num1 + min(min(min0, min1), min2);
		dp_min[2] = num2 + min(min1, min2);
	}

	cout << max(max(dp_max[0], dp_max[1]), dp_max[2]) << " " << min(min(dp_min[0], dp_min[1]), dp_min[2]);
}