글 읽기 - 2차원 배열 때문에 생기는 시간초과 인가요??

sons 7년 전 0

다른 분들 코드 보면 되게 복잡해 보이고, 저렇게 까지 할 필요가 있나 싶어서

저는 그냥 그림과 같은 2차원 배열 하나에 지나가는 자리만 체크하고 뱀의 머리가 경계를 넘거나 지나간 자리에 가는 순간까지 걸리는 시간을 체크하는 식으로 해봤는데 답은 다 맞았습니다

문제 예시랑 게시판 질문 답글에 달린 반례들이요. 근데 시간초과가 떠서 통과를 못하는데 어떻게 해결할 수 있을까요?

#include <cstdio>

#define MAX_L 1001

int map[2*(MAX_L)+1][2*(MAX_L)+1];
int L, rotate;
int total;
int head_x, head_y;

int dist[MAX_L];
char dir[MAX_L];
char prev_dir;

bool check(int head_x, int head_y)
{
	if(map[head_y][head_x] == 1) return false;
	else if(head_x < 1 || head_x > (2*L) + 1) return false;
	else if(head_y < 1 || head_y > (2*L) + 1) return false;
	else return true;
}


bool first_move(int k, char dir)
{
	for(int i=1; i<= k ; i++)
	{
		total++;

		if(!check(++head_x, head_y))
			return false;
		else
			map[head_y][head_x] = 1;
	}
	prev_dir = 'R';
	return true;
}

bool move(int k, char dir)
{
	char next_dir;

	if(dir == 'R')
	{
		if(prev_dir == 'R')
			next_dir = 'D';
		else if(prev_dir == 'L')
			next_dir = 'U';
		else if(prev_dir == 'U')
			next_dir = 'R';
		else if(prev_dir == 'D')
			next_dir = 'L';

	}else if(dir == 'L')
	{
		if(prev_dir == 'R')
			next_dir = 'U';
		else if(prev_dir == 'L')
			next_dir = 'D';
		else if(prev_dir == 'U')
			next_dir = 'L';
		else if(prev_dir == 'D')
			next_dir = 'R';
	}else
	{
		printf("invalid direction\n");
		return false;
	}


	if(next_dir == 'R')
	{
		for(int z = 1; z <= k ; z++)
		{
			total++;
		
			if(!check(++head_x, head_y))
				return false;
			else
				map[head_y][head_x] = 1;
		}
		prev_dir = 'R';
	}
	else if(next_dir == 'L')
	{
		for(int z = 1; z<=k ;z++)
		{
			total++;

			if(!check(--head_x, head_y))
				return false;
			else
				map[head_y][head_x] = 1;
		}
		prev_dir = 'L';
	}
	else if(next_dir == 'U')
	{
		for(int z = 1; z<= k; z++)
		{
			total++;
			if(!check(head_x, --head_y))
				return false;
			else
				map[head_y][head_x] = 1;
		}
		prev_dir = 'U';
	}
	else if(next_dir == 'D')
	{
		for(int z =1; z<= k ; z++)
		{
			total++;
			if(!check(head_x, ++head_y))
				return false;
			else
				map[head_y][head_x] = 1;
		}
		prev_dir = 'D';
	}

	return true;
}


int main(void)
{
	freopen("a.txt", "r", stdin);
	scanf("%d", &L);
	scanf("%d", &rotate);

	dir[0] = 'R';
	head_x = L+1;
	head_y = L+1;

	for(int i=1; i<= rotate; i++)
		scanf("%d %c", &dist[i], &dir[i]);

	map[head_y][head_x] = 1;

	for(int i=1; i<= rotate; i++)
	{
		if(i == 1)
		{	
			if(!first_move(dist[i], dir[i-1]))
				break;
		}else
		{
			if(!move(dist[i], dir[i-1]))
				break;
		}
 	}	

	printf("%d", total);
}

dotorya 7년 전 0

dist[i]가 최대 10^8이라서 최악의 경우 N * dist[i] ~ 10^11번 이상 연산을 수행하므로, 시간초과가 날듯 합니다.

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

문제

문제

출처

ICPC

2차원 배열 때문에 생기는 시간초과 인가요??

sons 7년 전 0

dotorya 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말