백준 - 2096 내려가기

접근방식

이 문제 역시 n의 값이 100,000이기 때문에 이중 포문으로는 해결이 안될거라 생각하고 다른 방식 있는지 살펴봤다.

해당 문제는 dp 문제에 가깝다고 생각했고 천천히 살펴 본 결과 

 

0번째 배열의 값은 아래의 0, 1 번 배열의 값을 더한 값,

1번째 배열의 값은 아래의 0,1,2번 배열의 값을 더한 값,

2번째 배열의 값은 아래의 1,2번 배열의 값을 더한 값 이라는걸 이용하면 될 거라고 생각했다. 

 

그래서 규칙을 찾고 식을 세워 접근했다. 

위에서 부터 값을 계산해서 배열의 값을 변경하는것보다 아래의 값부터 위로 올라오는 방식을 택했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;


int max_dp[100001][3];
int min_dp[100001][3];

int main() {

	int n;
	cin >> n;

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

		int x, y, z;
		cin >> x >> y >> z;

		max_dp[i][0] = x;
		max_dp[i][1] = y;
		max_dp[i][2] = z;

		min_dp[i][0] = x;
		min_dp[i][1] = y;
		min_dp[i][2] = z;

	}

	for (int i = n-1; i >= 1; i--) {

		max_dp[i-1][0] = max((max_dp[i-1][0] + max_dp[i][0]) , (max_dp[i-1][0] + max_dp[i][1]));
		max_dp[i-1][1] = max({(max_dp[i-1][1] + max_dp[i][0]), (max_dp[i-1][1] + max_dp[i][1]), (max_dp[i-1][1] + max_dp[i][2])});
		max_dp[i-1][2] = max((max_dp[i-1][2] + max_dp[i][1]), (max_dp[i - 1][2] + max_dp[i][2]));
	
		min_dp[i-1][0] = min((min_dp[i-1][0] + min_dp[i][0]), (min_dp[i-1][0] + min_dp[i][1]));
		min_dp[i-1][1] = min({ (min_dp[i-1][1] + min_dp[i][0]), (min_dp[i-1][1] + min_dp[i][1]), (min_dp[i-1][1] + min_dp[i][2]) });
		min_dp[i-1][2] = min((min_dp[i-1][2] + min_dp[i][1]), (min_dp[i-1][2] + min_dp[i][2]));
	}




	int result_max = max({ max_dp[0][0], max_dp[0][1], max_dp[0][2] });
	int result_min = min({ min_dp[0][0], min_dp[0][1], min_dp[0][2] });


	cout << result_max << " " << result_min;
	return 0;
}

 

풀이 방법

1. max_dp, min_dp에 값을 입력 받아서 초기화해준다.

2. for 문 한번을 이용해서 n-1 부터 1까지 i의 값을 감소하면서 max_dp와 min_dp의 값을 갱신해준다. 

 

하지만 .....

결과는 정상 출력되는거 같은데... 메모리 초과가 났다......

 

수정 코드 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int max_dp[3] = { 0, };
int min_dp[3] = { 0, };
int max_result[3] = { 0, };
int min_result[3] = { 0, };

int main() {

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;

		max_dp[0] = max_result[0];
		max_dp[1] = max_result[1];
		max_dp[2] = max_result[2];

		max_result[0] = x + max(max_dp[0], max_dp[1]);
		max_result[1] = y + max({ max_dp[0], max_dp[1], max_dp[2] });
		max_result[2] = z + max(max_dp[1], max_dp[2]);
		
		
		min_dp[0] = min_result[0]; 
		min_dp[1] = min_result[1];
		min_dp[2] = min_result[2];

		min_result[0] = x + min(min_dp[0], min_dp[1]);
		min_result[1] = y + min({ min_dp[0], min_dp[1], min_dp[2] });
		min_result[2] = z + min(min_dp[1], min_dp[2]);
	}

	int result_max = max({ max_result[0], max_result[1], max_result[2] });
	int result_min = min({ min_result[0], min_result[1], min_result[2] });



	cout << result_max <<" "<<result_min;
	return 0;
}