[C++] 백준 2096번 내려가기

다이나믹 프로그래밍 문제.

메모리 제한이 상당히 제약적인데, 이 부분을 잘 이해했으면 쉽게 풀 수 있는 문제다.

처음에 배열을 10만 x 3개씩 만들어서 풀어보려 했는데, 메모리 초과가 났다.

결국 게시판을 참고해서 풀 수 있었다.

 

문제풀이

문제에 표현된 그대로, N번째 줄마다 1, 2, 3번째에 도달했을 때 최대, 최소값을 기록해두면 된다.

• 첫번째 칸에 도달한 경우에는 이전에 1, 2번째 칸인 경우이다.
• 두번째 칸에 도달한 경우에는 이전에 1, 2, 3번째 칸인 경우이다.
• 세번째 칸에 도달한 경우에는 이전에 2, 3번째 칸인 경우이다.

 

이 문제의 핵심은 이전에 지나온 칸, 앞으로 지나올 칸의 수는 저장할 필요가 없다는 것이다.

따라서 입력을 받을 때마다 i번째 칸에서의 최대, 최소값을 기록해두면 된다.

기록할 때, 이전 값을 덮어씌우게 되면 2, 3번째에서 이상한 값이 될 수 있으므로

이전 값을 기록할 배열을 하나 또 만들어둬야 한다.

 

코드전문

 

/*
* 백준 2096번 내려가기
* https://www.acmicpc.net/problem/2096
* 다이나믹 프로그래밍
* 
* 해결책 : 1. 이미 지나온 부분 / 앞에 만날 부분을 저장할 필요가 없다.
* 2. 이전 값을 저장해줘야 한다.
* https://www.acmicpc.net/board/view/23024 에 있는 반례를 참고했음.
*/
#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[4];
int dp_save_max[4];
int dp_save_min[4];
int dp_max[4];
int dp_min[4];
int maxAns = 0;
int minAns = 1000000;

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 3; j++) {
			cin >> arr[j];
		}
		for (int j = 1; j <= 3; j++) {
			if (i == 1) {
				dp_save_max[j] = arr[j];
				dp_save_min[j] = arr[j];
			}
			else {
				if (j == 1) {
					dp_save_max[j] = arr[j] + max(dp_max[j], dp_max[j + 1]);
					dp_save_min[j] = arr[j] + min(dp_min[j], dp_min[j + 1]);
				}
				else if (j == 2) {
					dp_save_max[j] = arr[j] + max(max(dp_max[j - 1], dp_max[j]), dp_max[j + 1]);
					dp_save_min[j] = arr[j] + min(min(dp_min[j - 1], dp_min[j]), dp_min[j + 1]);
				}
				else {
					dp_save_max[j] = arr[j] + max(dp_max[j - 1], dp_max[j]);
					dp_save_min[j] = arr[j] + min(dp_min[j - 1], dp_min[j]);
				}
			}
		}
		for (int j = 1; j <= 3; j++) {
			dp_max[j] = dp_save_max[j];
			dp_min[j] = dp_save_min[j];
		}
	}

	for (int i = 1; i <= 3; i++) {
		maxAns = max(maxAns, dp_max[i]);
		minAns = min(minAns, dp_min[i]);
	}

	cout << maxAns << " " << minAns;

	return 0;
}

dp_max, dp_min가 최종적으로 결정되는 값.

dp_save_max, dp_save_min 값이 계산한 최대 최소값을 저장해둘 temp배열이다.

 

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.