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

 

다이나믹 프로그래밍 문제입니다.

 

N줄에 숫자가 3개씩 적혀있는데 아래로 내려가거나, 바로 아래와 인접해 잇는곳으로만 내려갈 수 있습니다.

이 때 얻을 수 있는 가장 큰 점수와 작은 점수를 구하는 문제입니다.

 

각각의 위치에서 현재 값과 내려가면서 선택할 수 있는 가장 큰 값을 maxDP에 저장합니다.

n의 줄까지 이를 반복하여 각위치의 최대값들을 비교해서 가장 큰값을 출력합니다.

#include <iostream>
#include <algorithm>
using namespace std;

int map[100010][3];
int minDP[3];
int maxDP[3];

void init()
{
	for (int i = 0; i < 100010; ++i) {
		for (int j = 0; j < 3; ++j) {
			map[i][j] = 0;
		}
	}
}

int main(int argc, char *argv[])
{
	int x, y, z;
	int n;
	cin >> n;

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

	maxDP[0] = map[1][0];
	maxDP[1] = map[1][1];
	maxDP[2] = map[1][2];

	minDP[0] = map[1][0];
	minDP[1] = map[1][1];
	minDP[2] = map[1][2];

	for (int i = 2; i <= n; ++i) {
		x = maxDP[0];
		y = maxDP[1];
		z = maxDP[2];

		maxDP[0] = max(x, y) + map[i][0];
		maxDP[1] = max({ x, y, z }) + map[i][1];
		maxDP[2] = max(y, z) + map[i][2];

		x = minDP[0];
		y = minDP[1];
		z = minDP[2];

		minDP[0] = min(x, y) + map[i][0];
		minDP[1] = min({ x, y, z }) + map[i][1];
		minDP[2] = min(y, z) + map[i][2];
	}

	cout << max({ maxDP[0], maxDP[1], maxDP[2] }) << " " << min({ minDP[0], minDP[1], minDP[2] }) << endl;

	return 0;
}