[Baekjoon] 2096번: 내려가기

🥅 문제

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

 

🔍 설계

전 줄까지의 결과에 새로운 줄에 입력받은 수를 더하여 최대 최소를 구하는 다이나믹 프로그래밍 문제이다.

 

처음 메모리 제한을 보지 않고, 100000줄을 다 받았는데, 메모리 초과가 발생하였다.

 

새로운 줄에 입력받을 수와 전 줄까지의 점수, 새로운 줄까지의 점수만 필요하므로 벡터를 3개만 생성한다.

 

다이나믹 프로그래밍에서는 초기화가 항상 중요한데, 첫째 줄까지의 점수는 입력받은 수 그대로이다. 

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, col;
int dy[] = { -1,0,1 };
vector<int> new_line(3);
vector<pair<int, int>> before_score(3, { 0, 1e9 + 7 });
vector<pair<int, int>> new_score(3, { 0, 1e9 + 7 });

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < 3; i++) {
		cin >> new_line[i];
		for (int j = 0; j < 3; j++) {
			before_score[i].first = new_line[i];
			before_score[i].second = new_line[i];
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> new_line[j];
			for (int k = 0; k < 3; k++) {
				col = j + dy[k];
				if (col >= 0 && col < 3) {
					new_score[j].first = max(new_score[j].first, before_score[col].first + new_line[j]);
					new_score[j].second = min(new_score[j].second, before_score[col].second + new_line[j]);
				}
			}
		}
		before_score = new_score;
		new_score = vector<pair<int, int>> (3, { 0, 1e9 + 7 });
	}

	int max_result = 0;
	int min_result = 1e9 + 7;
	for (int i = 0; i < 3; i++) {
		max_result = max(max_result, before_score[i].first);
		min_result = min(min_result, before_score[i].second);
	}
	cout << max_result << " " << min_result << "\n";

	return 0;
}