백준 2096 내려가기 C++

문제

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

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

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

입력

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

출력

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

풀이

최대 점수와 최소 점수를 따로 계산을 해주었다.

최대 점수를 구하는 점화식으로 아래의 식을 사용하였다.

DP[0] =  max(DP[0], DP[1]) + arr[0]

DP[1] =  max(max(DP[0], DP[1]),max) + arr[1]

DP[2] =  max(DP[1], DP[2]) + arr[2]

 

최소 점수를 구하는 점화식으로는 아래의 식을 사용하였다.

DP[0] =  min(DP[0], DP[1]) + arr[0]

DP[1] =  min(min(DP[0], DP[1]),max) + arr[1]

DP[2] =  min(DP[1], DP[2]) + arr[2]

코드

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

int arr[100001][3] = { 0 };
int DP[6] = { 0 };
int prev_DP[6] = { 0 };

int main(void) {
	int N;
	int solve = 0;
	int min_solve = 0;
	cin >> N;

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

	}

	for (int i = 1; i < N; i++) {
		prev_DP[0] = DP[0];
		prev_DP[1] = DP[1];
		prev_DP[2] = DP[2];
		prev_DP[3] = DP[3];
		prev_DP[4] = DP[4];
		prev_DP[5] = DP[5];
		for (int j = 0; j < 3; j++) {
			
			if (j == 1) {
				solve = max(prev_DP[j], prev_DP[j + 1]);
				DP[j] = arr[i][j] + max(solve, prev_DP[j - 1]);
				min_solve = min(prev_DP[j + 3], prev_DP[j+2]);
				DP[j + 3] = arr[i][j] + min(min_solve, prev_DP[j+4]);
			}
			else if (j == 2) {
				DP[j] = arr[i][j] + max(prev_DP[j-1] , prev_DP[j]);
				DP[j + 3] = arr[i][j] + min(prev_DP[j + 2] , prev_DP[j + 3] );
			}
			else {
				DP[j] = arr[i][j]+ max(prev_DP[j+1] , prev_DP[j]);
				DP[j + 3] = arr[i][j] + min(prev_DP[j + 4], prev_DP[j + 3]);
			}
		
	}
}
	

	solve = max(max(DP[0], DP[1]), DP[2]);
	min_solve = min(min(DP[3], DP[4]), DP[5]);
	cout << solve << " " << min_solve << endl;
	return 0;
}