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


[ 알고리즘풀이 ]

 이 문제는 전형적인 쉬운 2차원 DP 문제이나, 4MB 라는 메모리 제한 때문에 배열 선언에 제약이 걸려있는 문제입니다. 따라서, 2행 3열짜리 2차원 배열을 선언해서 첫 번째 행에는 현재까지 가장 큰 값, 가장 작은 값을 저장하고 두 번째 행에는 들어온 입력값과 첫 번째 행의 값을 이용해 새롭게 가장 큰 값, 가장 작은 값은 갱신해줍니다. 그 후, 두 번째 행을 첫 번째 행에 덮어가며 N행 3열 2차원 배열이 아닌 2행 3열 2차원 배열로 문제를 해결할 수 있습니다.

 

ansMap[0][j].first : 현재까지 j번 째 열에서 얻을 수 있는 가장 큰 값

ansMap[0][j].second : 현재까지 j번 째 열에서 얻을 수 있는 가장 작은 값

#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, map[3] = {};
	pair<int, int> ansMap[2][3] = {};

	cin >> N;
	cin >> map[0] >> map[1] >> map[2];
	for (int j = 0; j < 3; j++) {
		ansMap[0][j].first = ansMap[0][j].second = map[j];
	}

	for (int i = 1; i < N; i++) {
		cin >> map[0] >> map[1] >> map[2];
		ansMap[1][0].first = max(ansMap[0][0].first, ansMap[0][1].first) + map[0];
		ansMap[1][0].second = min(ansMap[0][0].second, ansMap[0][1].second) + map[0];
		ansMap[1][1].first = max({ ansMap[0][0].first, ansMap[0][1].first, ansMap[0][2].first }) + map[1];
		ansMap[1][1].second = min({ ansMap[0][0].second, ansMap[0][1].second, ansMap[0][2].second }) + map[1];
		ansMap[1][2].first = max(ansMap[0][1].first, ansMap[0][2].first) + map[2];
		ansMap[1][2].second = min(ansMap[0][1].second, ansMap[0][2].second) + map[2];
		for (int j = 0; j < 3; j++)
			ansMap[0][j].first = ansMap[1][j].first, ansMap[0][j].second = ansMap[1][j].second;
	}
	cout << max({ ansMap[0][0].first, ansMap[0][1].first, ansMap[0][2].first }) << ' ' << min({ ansMap[0][0].second, ansMap[0][1].second, ansMap[0][2].second });
}

 

+ Recent posts