글 읽기 - [1799] 메모리초과가 납니다.

irnd04 5년 전 0

input에 가능한 좌표

pos에 놓는 좌표

재귀로 직접 놓으면서 검사하는 소스인데요

메모리초과가 나서요.. 재귀로 풀 수 없는 문제일까요?

chk함수로 가지를 쳐서 나름(?) 재귀를 안태웠는데도 메모리초과가 납니다.

시간초과면 몰라두 메모리초과가 나서 당황스럽습니다.

메모리 초과를 해결할 수 있는 방법이 있을까요?

#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct Node {
	short y;
	short x;
	Node(short y, short x) {
		this->y = y;
		this->x = x;
	}
};

Node* pos[100];
Node* input[100];

short n;
short input_size;
short res;

bool chk(short y, short x, short size) {

	Node* cur = 0;
	
	for (short i = 0; i < size; i++) {
		cur = pos[i];
		if (abs(cur->y - y) == abs(cur->x - x))
			return false;
	}
	return true;
}

void solve(short s, short p) {
	Node* cur = 0;
	res = max(res, p);
	for (short i = s; i < input_size; i++) {
		cur = input[i];
		if (chk(cur->y, cur->x, p)) {
			pos[p] = new Node(cur->y, cur->x);
			solve(i + 1, p + 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	short x;
	cin >> n;

	for (short i = 0; i < n; i++) {
		for (short j = 0; j < n; j++) {
			cin >> x;
			if (x == 1)
				input[input_size++] = new Node(i, j);
		}
	}

	solve(0, 0);

	cout << res << '\n';
	return 0;
}

irnd04 5년 전 1

해결했습니다. 메모리 해제 때문이군요..

c++더 배워서 써야겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[1799] 메모리초과가 납니다.

irnd04 5년 전 0

irnd04 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말