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

문제링크: https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

쉬운 dp 문제입니다.

 

윗단의 값들을 통해서 점화식을 유추할 수 있습니다.

 

//1.
dp[i][0] = arr[i][0] + max(dp[i - 1][0], dp[i - 1][1]);
//2.
dp[i][1] = arr[i][1] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
//3.
dp[i][2] = arr[i][2] + max(dp[i - 1][1], dp[i - 1][2]);

 

왼쪽은 왼쪽이랑 가운데로 부터, 가운데는 3군데 모두, 오른쪽은 오른쪽이랑 가운데로 부터 올 수있기 때문입니다.

 

다만 시간초과를 조심하셔야 합니다. 

4 MB이기 때문에 메모리 제한에 주의하셔야 합니다. 

arr같은경우 값을 전부 받고 dp는 dp[2][3] 으로 이전값과 현재 dp 값을 저장하는 용도로 사용하였습니다. 

(arr도 더 줄일 수 있는 문제였습니다.) 

 

 

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
int arr[100000][3] = { 0 };
int maxed[2][3] = { 0 };
int mined[2][3] = { 0 };
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

	maxed[0][0] = mined[0][0] = arr[0][0];
	maxed[0][1] = mined[0][1] = arr[0][1];
	maxed[0][2] = mined[0][2] = arr[0][2];

	for (int i = 1; i < n; i++) {
		maxed[1][0] = arr[i][0] + max(maxed[0][0], maxed[0][1]);
		maxed[1][1] = arr[i][1] + max(max(maxed[0][0], maxed[0][1]), maxed[0][2]);
		maxed[1][2] = arr[i][2] + max(maxed[0][1], maxed[0][2]);

		maxed[0][0] = maxed[1][0];
		maxed[0][1] = maxed[1][1];
		maxed[0][2] = maxed[1][2];

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

		mined[0][0] = mined[1][0];
		mined[0][1] = mined[1][1];
		mined[0][2] = mined[1][2];

	}
	cout << max(max(maxed[0][0], maxed[0][1]), maxed[0][2]) << ' ' << min(min(mined[0][0], mined[0][1]), mined[0][2]) << endl;

}