[C++] 백준 2096번: 내려가기

문제 링크

2096번: 내려가기

문제 요약

N개의 줄이 있고, 각 줄에는 3칸이 있다. 각 칸에는 숫자가 있다. 아래 줄로 내려갈 때, 바로 아래와 인접한 칸으로 이동할 수 있다. 이때, 이동하면서 거쳐가는 칸에 적힌 수의 합의 최댓값과 최솟값을 구해야 한다.

접근 방법

내려가기 2와 문제 지문은 정확하게 일치하지만, 메모리 제한이 C++ 기준 4MB이기 때문에, 그냥 배열을 선언해서 제출하면 MLE를 받을 수 있습니다. 풀이는 기본적으로 동일하되, 여태까지의 값을 저장하지 말고, 입력을 받으면서 값을 계산해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, res1, res2, arr[3], dp1[2][3], dp2[2][3];
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> arr[0] >> arr[1] >> arr[2];

		if (i == 1)
		{
			dp1[0][0] = dp2[0][0] = arr[0];
			dp1[0][1] = dp2[0][1] = arr[1];
			dp1[0][2] = dp2[0][2] = arr[2];
			continue;
		}

		dp1[1][0] = max(dp1[0][0], dp1[0][1]) + arr[0];
		dp1[1][1] = max(dp1[0][0], max(dp1[0][1], dp1[0][2])) + arr[1];
		dp1[1][2] = max(dp1[0][1], dp1[0][2]) + arr[2];

		dp2[1][0] = min(dp2[0][0], dp2[0][1]) + arr[0];
		dp2[1][1] = min(dp2[0][0], min(dp2[0][1], dp2[0][2])) + arr[1];
		dp2[1][2] = min(dp2[0][1], dp2[0][2]) + arr[2];

		for (int i = 0; i < 3; i++)
		{
			dp1[0][i] = dp1[1][i];
			dp2[0][i] = dp2[1][i];
		}
	}

	res1 = max(dp1[0][0], max(dp1[0][1], dp1[0][2]));
	res2 = min(dp2[0][0], min(dp2[0][1], dp2[0][2]));
	cout << res1 << ' ' << res2;
	return 0;
}