백준 1520 내리막 길

부제 : 아주 스트레스 받은 문제

#include <iostream>

using namespace std;
int height[501][501];
int memo[501][501];
int i_length, j_length;
int pX[4] = { -1, 1, 0, 0 };
int pY[4] = { 0, 0, -1, 1 };

int solve(int x, int y) {
	int& memoRef = memo[x][y];
	if (x == i_length - 1 && y == j_length) return 1;

	if (memoRef =! -1) return memoRef;


	int i, j;
	memoRef = 0;
	for (int k = 0; k < 4; k++) {
		i = x + pX[k];
		j = y + pY[k];
		if (height[i][j] < height[x][y] && i >= 0 && i < i_length && j >= 0 && j < j_length) {
			memoRef += solve(i, j);
		}
	}

	return memoRef;

}

void console_input() {
	cin >> i_length >> j_length;
	for (int i = 0; i < i_length; i++) {
		for (int j = 0; j < j_length; j++) {
			cin >> height[i][j];
		}
	}
}

int main() {
	console_input();
	for (int i = 0; i < i_length; i++) {
		for (int j = 0; j < j_length; j++) {
			memo[i][j] = -1;
		}
	}

	memo[i_length - 1][j_length - 1] = 1;
	cout << solve(0, 0) << endl;

	return 0;
}

이 문제는 그냥 풀면 시간 초과가 난다

시간초과가 5번 나길레 몇번 구글링했는데

전부 나랑 비슷한 코드라 도대체 뭐가 문제지.. 싶었다.

그러다가 백준 홈페이지에 질문을 뒤적거리다 결국 해법을 찾았다

해법은... 메모이제이션을 초기화 하는거..

원래 어떻게 풀었었나면, 메모이제이션을 0으로 놔둔 상태로, 메모이제이션의 값이 0보다 크면 리턴하게 했다

근데 그게 아니고, 메모이제이션이 -1일 경우에만 연산하도록 휴리스틱을 하나 넣어야 되는거였다.

흠 근데, 맨 처음에 구글링 하기 전에 이 방법을 썼는데도 시간초과가 났었어서,

아 이게 문제가 아닌갑다.. 하고 다른쪽으로 고민하다가

결국 안돼서 구글링 한거였는데.. 그냥 그거 계속 생각할걸 그랬다.. 너무 빨리 포기했다... ㅋㅋㅋㅋㅋㅋㅋ

처음에 저 휴리스틱을 썼는데도 시간초과가 난건, 아마 휴리스틱을 제대로 적용을 못시킨 탓이겠지..

조금 더 보면서 휴리스틱이 제대로 적용되나만 볼껄.. 

근데 또 웃긴건

나같은 사람이 한둘이 아닌게, 제출 현황을 보면 오답의 90%는 시간초과다 ㅋㅋ

뭐 그래도.. 메모이제이션의 초기화의 중요성을 2시간이라는 소중한 시간을 주고 배웠으니 잘 배웠네 뭐 ㅋㅋ

근데 제출을 10개나 날린게 좀 아깝다 

머리가 멍청하면 이렇게 고생하는구나...ㅠㅠ