백준 2096 내려가기

메모리를 줄이는게 관건인 문제

DP를 해서 풀되, 재귀로 풀지 말고 반복문으로 푼다.

DP[n][n] =  number[n][n] + max(DP[n-1][n], DP[n-1][n-1], DP[n-1][n+1])

여기서 최대 최소 둘다 출력해야 하니 때에 따라 max나 min을 쓰자.

여기까지는, 그리고 재귀로 짜는것까지는 매우 간단

하지만 난 왜 항상 재귀를 반복문으로 고치는게 힘들까

[현재 row에서 max나 min값을 구하기 위해선 'number의 이전 row의 값'과 'memo의 이전 row의 값' 이외엔 필요하지 않다]

를 아이디어로 반복문을 짜면 된다.

그렇게 짜고 나면 입력을 받는 number도 한 줄만 있으면 됨을 알수 있기 때문에 number에 들어가는 메모리도 절약된다.

그 후 다시 코드를 살펴보면,

굳이 memo 배열에 100001이나 되는 크기를 할당할 필요가 없다.

그냥 memo배열에 두줄만 주고 서로 왔다리 갔다리 하면 된다.

따라서 아래와 같은 코드로 메모리를 절약 가능하다.

#define _CRT_SECURE_NO_WARNINGS
#define MYMAX2(A,B) (((A)>(B))?(A):(B)) 
#define MYMAX3(A,B,C) ( MYMAX2( (MYMAX2((A),(B))) , (C)) )
#define MYMIN2(A,B) (((A)<(B))?(A):(B)) 
#define MYMIN3(A,B,C) ( MYMIN2( (MYMIN2((A),(B))) , (C)) )
#define INT_MAX_MY 2100000000;
#include <string.h>
#include <iostream>

using namespace std;


int memoMax[2][3];
int memoMin[2][3];
int arr[3];
int N;


int main(void) {
	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		scanf("%d %d %d", &arr[0], &arr[1], &arr[2]);
		memoMax[1][0] = MYMAX2(memoMax[0][0], memoMax[0][1]) + arr[0];
		memoMax[1][1] = MYMAX3(memoMax[0][0], memoMax[0][1], memoMax[0][2]) + arr[1];
		memoMax[1][2] = MYMAX2(memoMax[0][1], memoMax[0][2]) + arr[2];

		memoMin[1][0] = MYMIN2(memoMin[0][0], memoMin[0][1]) + arr[0];
		memoMin[1][1] = MYMIN3(memoMin[0][0], memoMin[0][1], memoMin[0][2]) + arr[1];
		memoMin[1][2] = MYMIN2(memoMin[0][1], memoMin[0][2]) + arr[2];


		for (int j = 0; j < 3; j++) {
			memoMax[0][j] = memoMax[1][j];
			memoMin[0][j] = memoMin[1][j];
		}

	}

	cout << MYMAX3(memoMax[1][0], memoMax[1][1], memoMax[1][2]) << " ";
	cout << MYMIN3(memoMin[1][0], memoMin[1][1], memoMin[1][2]);


	return 0;
}