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

안유태·2022년 10월 21일
0

알고리즘

목록 보기
60/239

2096번: 내려가기

dp를 활용한 문제이다. 다음 줄의 인접한 인덱스로 내려가면서 더한 최대 점수와 최소 점수를 구하면 된다. tmpdp 두 배열을 이용하여 문제를 해결했다. 처음 dp 배열에 A 배열의 첫 줄을 저장하고 maxSum 함수에 들어간다. 함수 내에서 tmp 배열에 dpA의 합의 최댓값을 구하여 저장하고 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;
}
profile
공부하는 개발자

0개의 댓글