백준 2096 : 내려가기

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

2096번: 내려가기

 

쉬운 DP문제다. 최대 숫자 30만개를 입력받아야하므로 메모리 제한 4mb이 빡센데, 일반적인 dp를 풀듯이 갱신하지 말고 갱신하고자 하는 줄과 바로 그 직전 줄만 보면 메모리 제한에 걸리지 않고 문제를 해결할 수 있다.

 

0. 이전에 수행한 연산이 이후의 연산에 영향을 미치므로 DP문제다.

1. 현재 줄을 갱신할 때는 (현재 위치에 있는 숫자) + (이전 줄에서 현재 위치로 올 수 있는 위치 중에서 가장 큰 값 or 가장 작은 값)을 더해준다.

3. i = 0 부터 n - 1까지 반복해주면 최대값 or 최소값을 구할 수 있다.

 

점화식으로 표현하자면 아래와 같다.

//최대값
A_n[0] = max(A_(n-1)[0], A_(n-1)[1])
A_n[1] = max(A_(n-1)[0], A_(n-1)[1], A_(n-1)[2])
A_n[2] = max(A_(n-1)[1], A_(n-1)[2])

//최소값
A_n[0] = min(A_(n-1)[0], A_(n-1)[1])
A_n[1] = min(A_(n-1)[0], A_(n-1)[1], A_(n-1)[2])
A_n[2] = min(A_(n-1)[1], A_(n-1)[2])

 

점화식에서 아래첨자 n은 n번째 줄을 의미한다. 점화식에서 보이는 것과 같이 n번째 줄을 갱신할 때 바로 직전의 결과(n -1)번째 줄의 결과만이 사용되므로 단순히 int[3] cur 배열과 int[3] prev 배열 두 개 만으로 문제를 해결할 수 있다.

 

초기에 주어지는 최대 30만개의 숫자도 int로 받아도 문제를 해결할 수 있지만, 입력으로 주어지는 수가 0 ~ 9로 1바이트 범위 내에서 서로 식별 가능하기 때문에 1바이트 자료구조인 char 배열로 받아 아스키코드 값을 기준으로 저장해줬다.

 

#include <iostream>

using namespace std;

int n;
char num[100'000][3];

int max(int a, int b, int c) { 
	a = a > b ? a : b;
	a = a > c ? a : c;
	return a;
}
int min(int a, int b, int c) {
	a = a < b ? a : b;
	a = a < c ? a : c;
	return a;
}

int DP(bool flag) {
	int prev[3] = { 0, };
	int cur[3];
	int min_default = 1e9;
	int max_default = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++)
			cur[j] = num[i][j];

		if (flag) {
			cur[0] += min(prev[0], prev[1], min_default);
			cur[1] += min(prev[0], prev[1], prev[2]);
			cur[2] += min(prev[1], prev[2], min_default);
		}
		else {
			cur[0] += max(prev[0], prev[1], max_default);
			cur[1] += max(prev[0], prev[1], prev[2]);
			cur[2] += max(prev[1], prev[2], max_default);
		}

		for (int j = 0; j < 3; j++)
			prev[j] = cur[j];
	}

	if (flag) return min(cur[0], cur[1], cur[2]);
	else return max(cur[0], cur[1], cur[2]);
}

void solution() {
	char tmp;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> tmp;
			num[i][j] = tmp - '0';
		}
	}

	cout << DP(0) << ' ';
	cout << DP(1);
}

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

	return 0;
}

메모리: 2312 kb

시간: 8 ms

 

참고로 char배열로 안하고 int배열로 입력받으면 아래와 같이 더 느리고 메모리도 더 많이 먹는다.

메모리: 3192 kb

시간: 20 ms