[C++][백준] 내려가기(2096) - DP

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

 

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

 

풀이

DP를 이용하여 문제를 해결할 수 있습니다.

dp[i][j]에는 (i, j) 위치까지 얻을 수 있는 최대 점수를 기록합니다.

 

다음으로 세가지 케이스를 생각해볼 수 있습니다.

 

1. 첫번째 위치에 있는 경우

첫번째 위치에 있으려면 이전 위치가 바로 위거나 윗줄 가운데 위치여야만 합니다.

따라서 dp[i-1][0], dp[i-1][1] 중 큰 값과 현재 위치 값을 더해준 값을 dp[i][j]에 기록합니다.

 

 

2. 가운데 위치에 있는 경우

가운데 위치에 있으려면 이전 위치가 바로 윗줄 어느 위치라고 상관이 없습니다.

따라서 dp[i-1][0], dp[i-1][1], dp[i-1][2]중 큰 값과 현재 위치 값을 더해준 값을 dp[i][j]에 기록합니다.

 

 

2. 오른쪽 위치에 있는 경우

첫번째 위치에 있으려면 이전 위치가 바로 위거나 윗줄 가운데 위치여야만 합니다.

따라서 dp[i-1][2], dp[i-1][1] 중 큰 값과 현재 위치 값을 더해준 값을 dp[i][j]에 기록합니다.

 

이때 입력되는 N의 범위는 (1 ≤ N ≤ 100,000)입니다.

해당 문제에서 100,000 x 3 배열을 만드는 경우 메모리 초과가 납니다.

 

사실 위 로직은 2 x 3 배열만으로도 충분히 구현 가능합니다.

새로운 정보는 무조건 첫줄에 기록되어 있습니다., 계산시에는 첫 줄의 정보를 활용하여 dp값을 갱신합니다.

갱신한 값은 다시 첫줄에 기록합니다. 

 

전체 코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int N;
const int MAX = 100010;
int dpMax[2][3];
int dpMin[2][3];

int max(int a, int b) {
	if (a < b) return b;
	else return a;
}

int min(int a, int b) {
	if (a < b) return a;
	else return b;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {

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

			if (i == 0) {
				dpMax[0][j] = dpMax[1][j] = num;
				dpMin[0][j] = dpMin[1][j] = num;
				continue;
			}

			if (j == 0) {
				dpMax[1][0] = max(dpMax[0][0], dpMax[0][1]) + num;
				dpMin[1][0] = min(dpMin[0][0], dpMin[0][1]) + num;
			}
			else if (j == 1) {
				dpMax[1][1] = max(max(dpMax[0][0], dpMax[0][1]), dpMax[0][2]) + num;
				dpMin[1][1] = min(min(dpMin[0][0], dpMin[0][1]), dpMin[0][2]) + num;
			}
			else if (j == 2) {
				dpMax[1][2] = max(dpMax[0][1], dpMax[0][2]) + num;
				dpMin[1][2] = min(dpMin[0][1], dpMin[0][2]) + num;
			}
		}
		dpMax[0][0] = dpMax[1][0];
		dpMax[0][1] = dpMax[1][1];
		dpMax[0][2] = dpMax[1][2];
		dpMin[0][0] = dpMin[1][0];
		dpMin[0][1] = dpMin[1][1];
		dpMin[0][2] = dpMin[1][2];
	}

	int resultMax = -1;
	int resultMin = 987654321;

	for (int i = 0; i < 3; i++) {
		if (resultMax < dpMax[0][i]) resultMax = dpMax[0][i];
		if (resultMin > dpMin[0][i]) resultMin = dpMin[0][i];
	}

	cout << resultMax << " " << resultMin;

	return 0;
}