백준2096 - 내려가기

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

2096번: 내려가기

처음에 2차원 배열을 이용한 DP로 접근했다가 메모리 초과 계속나서 1차원 배열을 이용한 DP로 해결한 문제다. 전에 있던 값을 다른 공간에 저장해놓았다가 규칙에 맞게 움직이면 된다.

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

int n;
int mat[3]; //현재 입력한 수
int res_big[3]; //최대만 찾아간 결과
int res_small[3]; //최소만 찾아간 결과

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> mat[0] >> mat[1] >> mat[2];

		if (i == 0) {
			res_big[0] = mat[0];
			res_big[1] = mat[1];
			res_big[2] = mat[2];

			res_small[0] = mat[0];
			res_small[1] = mat[1];
			res_small[2] = mat[2];
		}
		else {
			//전에 있던 큰 값을 미리 저장
			int temp1 = res_big[0];
			int temp2 = res_big[1];
			int temp3 = res_big[2];

			//전에 있던 작은 값을 미리 저장
			int temp4 = res_small[0];
			int temp5 = res_small[1];
			int temp6 = res_small[2];

			//최댓값 찾기
			res_big[0] = max(temp1, temp2) + mat[0]; //0번지는 전에 0번지, 1번지에서 찾아갈 수 있다.
			res_big[1] = max(max(temp1, temp2),temp3) + mat[1]; //1번지는 전에 0번지, 1번지, 2번지에서 찾아갈 수 있다.
			res_big[2] = max(temp2, temp3) + mat[2]; //2번지는 전에 1번지, 2번지에서 찾아갈 수 있다.

			//최솟값 찾기
			res_small[0] = min(temp4, temp5) + mat[0]; //0번지는 전에 0번지, 1번지에서 찾아갈 수 있다.
			res_small[1] = min(min(temp4, temp5), temp6) + mat[1]; //1번지는 전에 0번지, 1번지, 2번지에서 찾아갈 수 있다.
			res_small[2] = min(temp5, temp6) + mat[2]; //2번지는 전에 1번지, 2번지에서 찾아갈 수 있다.
		}
	}

	//큰 값 경로 중 가장 큰 값, 작은 값 경로 중 가장 작은 값을 출력
	cout << max(res_big[0], max(res_big[1], res_big[2])) << ' ' << min(res_small[0], min(res_small[1], res_small[2]));
}