[G5] 백준 2096번 내려가기 C++ 다이나믹 프로그래밍

리뷰

 

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

메모리 제한이 4MB인 문제

 

 

전역 변수

• N : 행의 최대 길이를 저장할 상수 변수
• n : 행의 길이를 저장할 변수
• lst : 수 정보를 저장할 배열
• dp : 최소 및 최대값을 저장할 배열
• pre : 이전 dp값을 저장할 배열

 

함수

없음

 

 

문제풀이

1. n을 입력 받고, n * 3크기의 숫자를 입력 받아 lst배열에 저장한다.
2. 첫 행에 저장된 수를 dp배열에 초기화 해준다.
3. 1 ~ n - 1행을 순회하며 각 dp의 열에 저장된 값을 pre배열에 복사해 준다.
4. 다시 3개의 열을 순회하며 각각 이동할 수 있는 위치 중 최소값 및 최대값을 갱신해 준다.
5. 모든 탐색을 마친 후 dp배열의 0번 인덱스의 3열 중 가장 큰 값을 출력해 주고, 공백으로 구분해 준다.
6. dp배열의 1번 인덱스의 3열 중 가장 작은 값을 출력해 준다.

 

트러블 슈팅

1. 다익스트라로 접근 했다가 바로 메모리 초과를 받았다.
2. 일반적인 N + 1 * 3의 DP배열을 초기화 하더라도 메모리 초과를 면하진 못할 것 같았다.
3. 따라서 매번 dp값을 pre배열에 복사하고, 갱신해 주는 느낌으로 진행하니 AC를 받았다.

 

참고 사항

• 이 문제의 메모리 제한은 4 MB인데 N이 최대 10만이라 최대한 메모리 리소스를 잘 사용해야 한다.
• lst배열에 저장되는 값은 0 ~ 10이므로 char로 구현 시 메모리가 현저히 줄었다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5;
int n;
char lst[N][3];
int dp[3][2], pre[3][2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> lst[i][j];
			lst[i][j] -= '0';
		}
	}

	for (int i = 0; i < 3; ++i) {
		dp[i][0] = dp[i][1] = lst[0][i];
	}

	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 3; ++j) {
			pre[j][0] = dp[j][0];
			pre[j][1] = dp[j][1];
		}

		for (int j = 0; j < 3; ++j) {
			if (j == 0) {
				dp[j][0] = lst[i][j] + max(pre[j][0], pre[j + 1][0]);
				dp[j][1] = lst[i][j] + min(pre[j][1], pre[j + 1][1]);
			}
			else if (j == 1) {
				dp[j][0] = lst[i][j] + max({ pre[j - 1][0], pre[j][0], pre[j + 1][0] });
				dp[j][1] = lst[i][j] + min({ pre[j - 1][1], pre[j][1], pre[j + 1][1] });
			}
			else {
				dp[j][0] = lst[i][j] + max(pre[j - 1][0], pre[j][0]);
				dp[j][1] = lst[i][j] + min(pre[j - 1][1], pre[j][1]);
			}
		}
	}
	cout << max({ dp[0][0], dp[1][0], dp[2][0] }) << " "
		<< min({ dp[0][1], dp[1][1], dp[2][1] });
}