백준2096 내려가기 - C++

최소값/최대값을 구하는 dp 문제이다.

다만 이 경우에 메모리가 4MB 가 한정되어 있으므로

최소한의 메모리를 사용하면 된다.

N 이 10만이고 3칸이므로 30만 x int = 1.2MB 정도를 차지하므로

dp 10만 짜리 배열을 하나 추가로 쓰거나 할 수 있지만

ladder 1 x 3 하나와 dp 2 x 3 2개로도 풀 수 있다.

귀찮아서 ladder 는 그냥 다 받기로 했다.

 

사다리는 다음과 같이 작동한다.

1 2 3 

4 5 6

이 있을 때, 1번은 4, 5 번,

2번은 4,5,6번

3번은 5,6 번으로만 내려갈 수 있으므로

4번의 최댓값은 max(1번 + 4번, 2번 + 4번) 이고, 최소값은 min(1번 + 4번, 2번 + 4번) 이다.

5번의 최댓값은 max(1번 + 5번, 2번 + 5번, 3번 + 5번) 이다.

6번의 최대값은 max(2번 + 6번, 3번 + 6번)이다.

이것을 감안하여 코드를 짜면 아래와 같다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int N;
int ladder[100001][3];
int dp[2][3][2];//N, 왼중오, 0=Max 1=Min

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", &ladder[i][j]);
		}
	}
	dp[0][0][0] = dp[0][0][1] = ladder[1][0];
	dp[0][1][0] = dp[0][1][1] = ladder[1][1];
	dp[0][2][0] = dp[0][2][1] = ladder[1][2];


	for (int i = 2; i <= N; i++) {
		//Min 구하기 위한 최댓값 설정
		//MAX 구할 때는 0이 최솟값
		dp[1][0][0] = dp[1][1][0] = dp[1][2][0] = 0;
		dp[1][0][1] = dp[1][1][1] = dp[1][2][1] = 1000000;
		for (int k = 0; k < 3; k++) {
			for (int j = 0; j < 3; j++) {
				if (k == 2 && j == 2) continue;
				if (k == 0 && j == 0) continue;
				dp[1][k][0] = max(dp[1][k][0], dp[0][k - 1 + j][0] + ladder[i][k]);
				dp[1][k][1] = min(dp[1][k][1], dp[0][k - 1 + j][1] + ladder[i][k]);
			}
		}
		dp[0][0][0] = dp[1][0][0];
		dp[0][1][0] = dp[1][1][0];
		dp[0][2][0] = dp[1][2][0];
		dp[0][0][1] = dp[1][0][1];
		dp[0][1][1] = dp[1][1][1];
		dp[0][2][1] = dp[1][2][1];
	}
	printf("%d %d\n", max(dp[0][0][0], max(dp[0][1][0], dp[0][2][0])), min(dp[0][0][1], min(dp[0][1][1], dp[0][2][1])));
	return 0;
}