#2096 내려가기

출처:https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

별모양이 3개의 칸 중 하나를 선택하며 밑으로 계속 내려가면서 거쳐간 경로의 최솟값 최댓값을 구하는 문제이다.

dp를 이용한 점화식을 구하여 해결하는 문제인데 처음에 dp의 배열을 dp[100001][3]과 같이 지정을 하면서 메모리의 초과가 일어났다. 하지만 dp를 dp[3]으로 지정하고 입력값만을 통해서도 계속해서 dp값을 갱신하면서 마지막 최댓값 최솟값을 구할 수 있다.

 

점화식 알고리즘은 다음과 같다.

 

현재 dp[0~2]= 전단계의 dp[0~2]중 최대 or 최솟값 + 현재 방문한 노드값(arr[0~2])

 

소스코드

 

	// #2096 내려가기
	#include <iostream>
	using namespace std;
	#include <cstring>
	#define endl '\n'
	int n;
	int dpmax[3];
	int dpmin[3];
	int tempmax[3];
	int tempmin[3];
	int arr[3];
	int MIN(int a, int b) {
	return a < b ? a : b;
	}
	int MAX(int a, int b) {
	return a > b ? a : b;
	}
	int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
	cin >> arr[0] >> arr[1] >> arr[2];
	if (i >= 1) {
	for (int j = 0; j < 3; j++) {
	if (j == 0) {
	tempmax[j] = MAX(dpmax[j], dpmax[j + 1]) + arr[j];
	tempmin[j] = MIN(dpmin[j], dpmin[j + 1]) + arr[j];
	}
	else if (j == 1) {
	tempmax[j] = MAX(dpmax[j], MAX(dpmax[j - 1], dpmax[j + 1])) + arr[j];
	tempmin[j] = MIN(dpmin[j], MIN(dpmin[j - 1], dpmin[j + 1])) + arr[j];
	}
	else {
	tempmax[j] = MAX(dpmax[j], dpmax[j - 1]) + arr[j];
	tempmin[j] = MIN(dpmin[j], dpmin[j - 1]) + arr[j];
	}
	}
	dpmax[0] = tempmax[0], dpmax[1] = tempmax[1], dpmax[2] = tempmax[2];
	dpmin[0] = tempmin[0], dpmin[1] = tempmin[1], dpmin[2] = tempmin[2];
	}
	if (i == 0) {
	dpmax[0] = dpmin[0] = arr[0];
	dpmax[1] = dpmin[1] = arr[1];
	dpmax[2] = dpmin[2] = arr[2];
	}
	}
	//memset(dpmin, -1, sizeof(dpmin));
	int maxx, minn;
	maxx = MAX(dpmax[0], MAX(dpmax[1], dpmax[2]));
	minn = MIN(dpmin[0], MIN(dpmin[1], dpmin[2]));
	cout << maxx << " " << minn << endl;
	}

view raw [BOJ]2096.cpp hosted with ❤ by GitHub