백준 - 2096번 : 내려가기 (C++)

풀이 방법 : DP

i-1번째에서 이동 가능한 곳의 값을 i번째의 값에 더해주면 된다.
예를 들면 i번째 줄의 0번 인덱스에는 i-1번째 줄의 0,1 번 인덱스에서 접근 가능하므로 둘 중에 더 큰 값을 더해주는 식으로 값을 갱신해나가면 최댓값이 구해진다.

같은 방법으로 더 작은 값을 더해주는 식으로 갱신해나가면 최솟값이 구해질 것이다.

풀이 방법 자체는 쉽지만 메모리 제한이 4MB이므로 DP테이블을 따로 만들어서 풀면 메모리 초과가 뜰 것이기에 그냥 크기 3짜리 배열을 최대, 최소 각각 하나씩 만들어서 값을 갱신해주었다.

#include <iostream>

using namespace std;

int Table[100000][3] = {};

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

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			cin >> Table[i][j];
		}
	}

	int Max[3] = {Table[0][0],Table[0][1],Table[0][2]};
	int Min[3] = { Table[0][0],Table[0][1],Table[0][2] };

	for (int i = 1; i < N; ++i)
	{
		int TempMax[3] = {};

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

		for (int j = 0; j < 3; ++j)
		{
			Max[j] += Table[i][j];
		}
	}

	int MaxAnswer = 0;
	
	for (int i = 0; i < 3; ++i)
	{
		MaxAnswer = max(MaxAnswer, Max[i]);
	}

	for (int i = 1; i < N; ++i)
	{
		Min[0] = min(Min[0], Min[1]);
		Min[2] = min(Min[2], Min[1]);
		Min[1] = min(Min[0], Min[2]);

		for (int j = 0; j < 3; ++j)
		{
			Min[j] += Table[i][j];
		}
	}

	int MinAnswer = 987654321;

	for (int i = 0; i < 3; ++i)
	{
		MinAnswer = min(MinAnswer, Min[i]);
	}

	cout << MaxAnswer << ' ' << MinAnswer;
}