재귀시 변수 선언에 유의

백준 1890번. 그냥 DFS + DP 문제로 아래 코드로는 무난히 돌아가지만

#include <iostream>

using namespace std;

int N;

int tile[100][100];
long long memo[100][100];

long long sol(int i, int j) {
	if (i == N - 1 && j == N - 1) {
		return 1;
	}
	if (memo[i][j] != -1) {
		return memo[i][j];
	}

	long long &ret = memo[i][j];
	ret = 0;
	if (i + tile[i][j] < N){
		ret += sol(i + tile[i][j], j);
	}
	if (j + tile[i][j] < N) {
		ret += sol(i, j + tile[i][j]);
	}

	return ret;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tile[i][j];
			memo[i][j] = -1;
		}
	}

	cout << sol(0, 0);
	return 0;
}#include <iostream>

using namespace std;

int N;

int tile[100][100];
long long memo[100][100];

long long sol(int i, int j) {
	if (i == N - 1 && j == N - 1) {
		return 1;
	}
	if (memo[i][j] != -1) {
		return memo[i][j];
	}


	long long ret = 0;
	if (i + tile[i][j] < N){
		ret += sol(i + tile[i][j], j);
	}
	if (j + tile[i][j] < N) {
		ret += sol(i, j + tile[i][j]);
	}
	memo[i][j] = ret;

	return ret;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tile[i][j];
			memo[i][j] = -1;
		}
	}

	cout << sol(0, 0);
	return 0;
}

중간에 sol 부분에서 변수를 하나 선언해서 쓰는 것으로 바뀌면 호출 스택에서 메모리를 무지 많이 써서 바로 메모리 초과가 뜬다

long long sol(int i, int j) {
	if (i == N - 1 && j == N - 1) {
		return 1;
	}
	if (memo[i][j] != -1) {
		return memo[i][j];
	}


	long long ret = 0;
	if (i + tile[i][j] < N){
		ret += sol(i + tile[i][j], j);
	}
	if (j + tile[i][j] < N) {
		ret += sol(i, j + tile[i][j]);
	}
	memo[i][j] = ret;

	return ret;
}

DFS를 재귀로 짤 때는 변수 선언에 유의하자.

Published Oct 6, 2018

algorithm

If I keep marking the dots, someday they will 🔗🔗Hyeungshik Jung on Twitter