백준 2096_내려가기(C++)

 

www.acmicpc.net/problem/2096

2096번: 내려가기

[문제 풀이]

dp를 이용하여 문제를 풀었습니다.

 

이 문제는 N X 3의 맵을 내려가며 최대 합과 최소 합을 구하는 문제였습니다.

최댓값, 최솟값을 구하기 위해 N X 3 dp배열을 선언할 경우 메모리 초과가 나게 됩니다. 따라서 max_dp[3], min_dp[3] 배열을 두어 한 줄씩 내려오며 각각 최댓값, 최솟값들을 저장해주면서 내려오는 식으로 문제를 해결했습니다.

[코드]

#include<iostream>
#include<algorithm>

using namespace std;

int N;

int input[3];
int max_dp[3];
int min_dp[3];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	cin >> max_dp[0] >> max_dp[1] >> max_dp[2];
	
	min_dp[0] = max_dp[0];
	min_dp[1] = max_dp[1];
	min_dp[2] = max_dp[2];

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

		int temp_0, temp_1, temp_2;

		cin >> input[0] >> input[1] >> input[2];

		temp_0 = max(max_dp[0], max_dp[1]) + input[0];
		temp_1 = max(max_dp[0], max(max_dp[1], max_dp[2])) + input[1];
		temp_2 = max(max_dp[1], max_dp[2]) + input[2];

		max_dp[0] = temp_0;
		max_dp[1] = temp_1;
		max_dp[2] = temp_2;

		temp_0 = min(min_dp[0], min_dp[1]) + input[0];
		temp_1 = min(min_dp[0], min(min_dp[1], min_dp[2])) + input[1];
		temp_2 = min(min_dp[1], min_dp[2]) + input[2];

		min_dp[0] = temp_0;
		min_dp[1] = temp_1;
		min_dp[2] = temp_2;
			
	}

	cout << max(max_dp[0], max(max_dp[1], max_dp[2])) << " " << min(min_dp[0], min(min_dp[1], min_dp[2])) << endl;

	return 0;

}