BOJ 2096 내려가기 / C++

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

2096번: 내려가기

 

아이디어

dp 문제라는 것을 쉽게 알아차릴 수 있지만 메모리제한이 4MB 밖에 안된다는 것을 보지 못한다면 실컷짜놓은 코드를 다 갈아 엎어야 할 수 있습니다.(본인처림)

슬라이딩 윈도우 알고리즘을 사용하여 3줄의 공간을 입력 받으면 다음 3줄의 공간을 입력 받기 전에 해당 구간까지의 최솟값과 최대값을 판단할 수 있는 배열을 업데이트 해주어야 합니다. 이 전략만 이해한다면 이후의 구현의 방법의 차이가 될 것 같습니다

 

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

vector<int> line;
vector<int> highest;
vector<int> lowest;
int n;

void solution() {
	cin >> n;
	line.resize(3,0);
	highest.resize(3,0);
	lowest.resize(3,0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> line[j];
		}
		if (i == 0) {
			highest = line;
			lowest = line;
			continue;
		}
		// 0 과 1, 1과 2에서 얻어낸 최댓값들을 비교하여 얻는 최댓값은 0, 1, 2의 최댓값이 됨
		highest[0] = max(highest[0], highest[1]);
		highest[2] = max(highest[1], highest[2]);
		highest[1] = max(highest[0], highest[2]) + line[1];
		highest[0] += line[0];
		highest[2] += line[2];

		lowest[0] = min(lowest[0], lowest[1]);
		lowest[2] = min(lowest[1], lowest[2]);
		lowest[1] = min(lowest[0], lowest[2]) + line[1];
		lowest[0] += line[0];
		lowest[2] += line[2];
	}
	cout << max(max(highest[0], highest[1]), highest[2]) << " " << min(min(lowest[0], lowest[1]), lowest[2]);
}


int main(void) {
	solution();
}
//https://www.acmicpc.net/problem/2096