[BOJ_C++] 2096번 : 내려가기

code

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h> 

using namespace std;

int maxdp[3][2];
int mindp[3][2];

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

	int n, temp1, temp2, temp3; cin >> n;
	
	maxdp[0][0] = maxdp[1][0] = maxdp[2][0] = 0;
	mindp[0][0] = mindp[1][0] = mindp[2][0] = 0;

	for (int i = 1; i <= n; i++) {
		cin >> temp1 >> temp2 >> temp3;
		maxdp[0][1] = max(maxdp[0][0], maxdp[1][0]) + temp1;
		maxdp[1][1] = max(maxdp[0][0], max(maxdp[1][0], maxdp[2][0])) + temp2;
		maxdp[2][1] = max(maxdp[1][0], maxdp[2][0]) + temp3;

		maxdp[0][0] = maxdp[0][1];
		maxdp[1][0] = maxdp[1][1];
		maxdp[2][0] = maxdp[2][1];

		mindp[0][1] = min(mindp[0][0], mindp[1][0]) + temp1;
		mindp[1][1] = min(mindp[0][0], min(mindp[1][0], mindp[2][0])) + temp2;
		mindp[2][1] = min(mindp[1][0], mindp[2][0]) + temp3;

		mindp[0][0] = mindp[0][1];
		mindp[1][0] = mindp[1][1];
		mindp[2][0] = mindp[2][1];

	}

	cout << max(maxdp[0][1], max(maxdp[1][1], maxdp[2][1])) << " " << min(mindp[0][1], min(mindp[1][1], mindp[2][1]));

	return 0;
}

• 각 위치에 올 수 있는 전 값들의 최소와 최대 값들을 계산하고 값과 더해주는 문제였다.
• 0번째 위치로 올 수 있는 경우는 전에 0번이나 1번에 있을 때이고, 1번에 올 수 있는 경우는 모든 경우, 3번에 올 수 있는 경우는 1번이나 2번에 있을 때이다.
• 이 문제에서 특이한 점은 주어진 메모리가 4MB로 매우 작다는 것이다. 따라서 dp의 모든 값을 기억하고 있는 것이 아닌 전 값만 기억하는 방법을 사용하였고, 최대 최소 값을 계산한 뒤 이전 값에 옮겨 넣어주었다. (옮겨 넣는 이유는 다음 값을 계산할때 이전 값이 아닌 앞에서 계산한 값이 들어갈 수 있기 때문)

결과