글 읽기 - 메모리 초과에 대한 이해 부족 ㅠㅠ...

jaydoubleu 6년 전 0

시간 초과는 line 만들어서 없앴는데..

메모리 초과 도저히 모르겠네요 ㅠㅠ.....

아직 메모리에 대한 개념을 잘 모르겠어요ㅠㅠㅠ

고수님들 도와주세요..

#include <cstdio>
#include <vector>
//#define MIN(A,B) A<B? A:B
using namespace std;

class snake {
public:
	int x;
	int y;
	snake(int a, int b) : x(a), y(b) {};
};


class line {
public:
	int sx;
	int sy;
	int dir; // 0 1 2 3
	int xory; //x = 1, y = -1
	int val; // x= ? or y = ?
	line(int a, int b, int c) : sx(a), sy(b), dir(c) {
		if (dir == 0 || dir == 2) {
			xory = -1;//y
			val = sy;
		}
		else {
			xory = 1; //x
			val = sx;
		}

	};
};

int L, N;
int now; //머리 방향
int order_sec[1001];
char order_dir[1001]; //R , L
int result;
int crush;
vector<snake> v;
vector<line> l;
vector<snake>::iterator  iter;

int X[] = { 1,0,-1, 0 }; //우 아래 좌 위
int Y[] = { 0,-1,0,1 };

bool iscrush() {
	int s = v.size();
	for (int i = 0; i < s - 2; i++) {
		if (v.at(i).x == v.back().x) {
			if (v.at(i).y == v.back().y) {
				return true;
			}
		}
	}
	return false;
}


bool isdead() {

	if (v.back().x < -1 * L || v.back().x > L || v.back().y < -1 * L || v.back().y > L) //벽 밖을 때
	{
		return true;
	}

	else
		return false;
}

int main() {
	now = 0; //우 0, 아래 1, 좌 2 위 3 (초기 오른쪽방향)
	result = 0; // 결과값 (초)
	crush = 0;
	scanf("%d", &L);
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %c", &order_sec[i], &order_dir[i]);
	}
	v.push_back(snake(0, 0));

	for (int i = 0; i < N; i++) {
		l.push_back(line(v.back().x, v.back().y, now));
		if (isdead() || crush)
			break;
		for (int j = 0; j < order_sec[i]; j++) {
			int newX = v.back().x + X[now];
			int newY = v.back().y + Y[now];
			v.push_back(snake(newX, newY));			
			result++;

			if (isdead())
				break;
			if (l.size() >= 4) {
				int xy = l.back().xory;
				for (int k = 0; k < l.size() - 3; k++) {
					if (xy != l.at(k).xory)
						if (iscrush()) {
							crush = 1;
							break;
						}
				}
				if (crush)
					break;
			}

		}
		if (order_dir[i] == 'R') {
			now = now + 1;
			if (now == 4)
				now = 0;
		}
		else if (order_dir[i] == 'L') {
			now = now - 1;
			if (now == -1)
				now = 3;
		}


	}
	printf("%d", result);

}

simm4256 6년 전 0

N의 범위가 10^8 입니다.

N번의 반복문에서 얼마나 많은 벡터값이 생성되는지 생각해보세요.

로직 자체를 변경하셔야 합니다.

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

문제

문제

출처

ICPC

메모리 초과에 대한 이해 부족 ㅠㅠ...

jaydoubleu 6년 전 0

simm4256 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말