글 읽기 - 뱀 문제 계속 런타임 에러가 나는데 원인을 모르겠습니다 .. 답변좀 부탁

matang1 7년 전 0

알고리즘 자체는 그냥 정말 단순하게 명령어대로 한칸한칸 이동하면서 걸린 시간을 재며 맵에 1을 입력하여 지나간걸 표시하고 맵 밖을 벗어난 좌표가 나오거나 한번 지나간 장소를 만나면 종료하는 알고리즘인데요

계속 런타임 에러가 나는데 무엇이 원인인지를 모르겠습니다.

문제에 있는 테스트케이스와 질문게시판에 검색해서 나오는 테스트케이스 몇개 돌려보면 정답은 맞게 출력이 되는것 같은데 도데체 원인이 뭘까요.. 답변좀 부탁드리겠습니다.

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;


int main(){

	long long int L, N; //L 맵의 중심으로부터의 넓이, N 총 회전하는 명령어의 수
	long long int timer = 0;
	bool stop_sw = false;

	long long int x, y; //현재 위치 저장 좌표
	int head=1; //1동, 2서, 3남, 4북

	cin >> L >> N;

	vector< vector<long long int> > iVector;  //2차원 동적배열

	for (int i = 0; i < L * 2 + 1; i++){
		vector<long long int> elem;
		elem.resize(L * 2 + 1);
		iVector.push_back(elem);
	}

	iVector[L][L] = 1; //맵의 시작위치에 1입력
	x = L;
	y = L;

	
	for (int i = 0; i < N && stop_sw == false; i++){
		long long int howlong; //명령어의 진행거리
		char LeftRight; //명령어의 회전하는 방향

		cin >> howlong >> LeftRight;

		for (long long int i = 0; i < howlong; i++){

			timer++;// 시간 늘려줌

			if (head == 1){ //바라보는 방향으로 한칸 전진하기 위한 좌표 수정
				x++;
			}
			else if (head == 2){
				x--;
			}
			else if (head == 3){
				y++;
			}
			else if (head == 4){
				y--;
			}
			
					
			if (x < 0 || y < 0 || x > L * 2 || y > L * 2){  //맵을 벗어난 좌표라면
				stop_sw = true;
				break;

			}
			else if (iVector[y][x] == 0){ //좌표 위치가 맵의 빈 공간이라면 1로 채움
				iVector[y][x] = 1;
			}
			else {				         //부딛힘 종료
				stop_sw = true;
				break;  
				
			}

		}//end for()

		if (LeftRight == 'L'){
			if (head == 1){
				head = 4;
			}
			else if (head == 2){
				head = 3;
			}
			else if (head == 3){
				head = 1;
			}
			else if (head == 4){
				head = 2;
			}
		}
		else if (LeftRight == 'R'){
			if (head == 1){
				head = 3;
			}
			else if (head == 2){
				head = 4;
			}
			else if (head == 3){
				head = 2;
			}
			else if (head == 4){
				head = 1;
			}
		}

	}//end for()

	if (stop_sw == false){ //명령어를 다 수행 했지만 어디에도 부딛치지 않았을 때
		while (stop_sw == false){
			timer++;// 시간 늘려줌

			if (head == 1){
				x++;
			}
			else if (head == 2){
				x--;
			}
			else if (head == 3){
				y++;
			}
			else if (head == 4){
				y--;
			}
			
			if (x < 0 || y < 0 || x > L * 2 || y > L * 2){  //맵을 벗어난 좌표라면
				stop_sw = true;
				break;

			}
			else if (iVector[y][x] == 0){   //좌표 위치가 맵의 빈 공간이라면 1로 채움
				iVector[y][x] = 1;
			}
			else {                    //부딛힘 종료
				stop_sw = true;
				break;  

			}
		}
	}



	printf("%d\n", timer);
	
	return 0;
}

kdk8361 7년 전 0

L이 1억까지인데 2억*2억개를 만드시네요

matang1 7년 전 0

염치 없지만 어느 부분을 수정해야되는지 여쭤봐도 될까요 ㅠㅠ 코딩 실력이 많이 낮아서 어느 부분을 말씀는건지 모르겠네요..

kdk8361 7년 전 0

이부분이 문제인데요. 사실 이건 고치는게 아니라 다른방식으로 하셔야 합니다.

L 제한이 1e8이라 뱀이 움직이는 배열을 그대로 구현하시면 최악의 경우 2e8 * 2e8 = 4e16이 됩니다.

long long은 8바이트라 3e17바이트가 되는데 이건 300pB(페타바이트) 가까이 되기 때문이죠.

    vector< vector<long long int> > iVector;  //2차원 동적배열

	for (int i = 0; i < L * 2 + 1; i++){
		vector<long long int> elem;
		elem.resize(L * 2 + 1);
		iVector.push_back(elem);
	}

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

문제

문제

출처

ICPC

뱀 문제 계속 런타임 에러가 나는데 원인을 모르겠습니다 .. 답변좀 부탁

matang1 7년 전 0

kdk8361 7년 전 0

matang1 7년 전 0

kdk8361 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말