백준 2096 내려가기 (C++)

2096번: 내려가기

dp를 활용한 문제이다. 다음 줄의 인접한 인덱스로 내려가면서 더한 최대 점수와 최소 점수를 구하면 된다. tmp와 dp 두 배열을 이용하여 문제를 해결했다. 처음 dp 배열에 A 배열의 첫 줄을 저장하고 maxSum 함수에 들어간다. 함수 내에서 tmp 배열에 dp와 A의 합의 최댓값을 구하여 저장하고 tmp와 스왑을 해준다. 이를 반복하면 중간 과정을 모두 저장할 필요 없이 최댓값을 구할 수 있따. minSum 또한 같은 방식으로 진행된다. 다만 minSum인 경우, 0이 있으면 이전의 값을 무시하고 0을 저장하므로 0인 경우와 아닌 경우로 분리해주었다.
처음에는 중간 과정을 모두 저장하여 메모리 초과가 발생했었다. 배열 두개를 사용하여 쉽게 해결할 수 있었다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, mmax = 0, mmin = 987654321;
int A[100001][3];
int tmp[3];
int dp[3];

void maxSum() {
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j == 0 && k == 2) continue;
				if (j == 2 && k == 0) continue;

				tmp[j] = max(tmp[j], dp[k] + A[i][j]);
			}
		}

		swap(dp, tmp);

		for (int j = 0; j < 3; j++) {
			tmp[j] = 0;
		}
	}

	for (int i = 0; i < 3; i++) {
		mmax = max(mmax, dp[i]);
	}
}

void minSum() {
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j == 0 && k == 2) continue;
				if (j == 2 && k == 0) continue;

				if (tmp[j] != 0) {
					tmp[j] = min(tmp[j], dp[k] + A[i][j]);
				}
				else {
					tmp[j] = dp[k] + A[i][j];
				}
			}
		}

		swap(dp, tmp);

		for (int j = 0; j < 3; j++) {
			tmp[j] = 0;
		}
	}

	for (int i = 0; i < 3; i++) {
		mmin = min(mmin, dp[i]);
	}
}

void solution() {
	for (int i = 0; i < 3; i++) {
		dp[i] = A[0][i];
	}

	maxSum();

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

	minSum();

	cout << mmax << " " << mmin;
}

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

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> A[i][j];
		}
	}

	solution();
	
	return 0;
}