글 읽기 - 메모리 초과가 나는데 도저희 메모리를 잡아먹을 부분이 어딘지 모르겠습니다...

boramatlulu 3년 전 0

TC는 일단 vs에서 돌렸을때 다맞았습니다.

보시면 전역변수로 거의 다 선언한데다가,

그나마 메모리좀 차지할 만 한게

int t_board[32][12];

이건데 이거도 사실 32*12*4byte라 주어진 조건인 512MB에는 한참이나 많이 남은것같은데

자꾸 메모리 초과가 떠서 어디가 잘못된 건지 잘 모르겠습니다 ㅜㅜㅜ 도와주세요....

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

struct Sadari {
	int x, y, kind;
};

Sadari make_sadari(int a, int b, int c) {
	Sadari temp;
	temp.x = a, temp.y = b, temp.kind = c;
	return temp;
}

int N, M, H, a, b;
int t_board[32][12];
vector<Sadari> v;
bool is_finished = false;
int ans = -1;
int lineIdx;

int sadariResult(int x, int y) {
	if (x == H + 1) { 
		return y; 
	}
	else {
		int nx = x + 1;
		int ny = y;
		if (t_board[nx][y] != 0) {	// 사다리가 있는 경우
			if (y - 1 > 0 && t_board[nx][y] == t_board[nx][y - 1]) ny = y -1 ;
			else ny = y + 1;
		}
		sadariResult(nx, ny);
	}
}

void simulate() {
	for (int i = 1; i <= N; i++) 
		if (sadariResult(0, i) != i) return;

	is_finished = true;
}

void doRecursion(int current, int target) {
	if (current >= target && !is_finished) simulate();
	else {
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j < N; j++) {
				if (t_board[i][j-1] == 0 && t_board[i][j] == 0 && t_board[i][j + 1] == 0  && t_board[i][j + 2] == 0 && !is_finished) {
					t_board[i][j] = lineIdx, t_board[i][j + 1] = lineIdx++;
					doRecursion(current + 1, target);
					t_board[i][j] = 0, t_board[i][j + 1] = 0;
					lineIdx--;
				}
			}
		}
	}
}

void init() {	// 초기화
	lineIdx = M + 1;
	memset(t_board, 0, sizeof(t_board));
	for (int i = 0; i < v.size(); i++) {
		Sadari s = v[i];
		t_board[s.x][s.y] = s.kind;
	}
}

int main() {
	cin >> N >> M >> H;
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		v.push_back(make_sadari(a, b, i)), v.push_back(make_sadari(a, b+1, i));
	}

	for (int line_num = 0; line_num <= 3; line_num++) {
		init();
		doRecursion(0, line_num);

		if (is_finished) {
			ans = line_num;
			break;
		}
	}
	
	cout << ans;
	return 0;
}