글 읽기 - 시간초과문제!!!

wjavm2 4년 전 0

자꾸 기출문제푸는데 구현부분에서 시간초과가 나네요ㅠㅠ

무엇때문에 나는걸까요??ㅠㅠ 조언좀 부탁드립니다!!!!!

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int R, C, M;
int Ocean[150][150] = { -1, };
struct Shark { int x,y, speed, dir, size; };
Shark info[150][150] = { 0 };

queue<Shark>Q;
vector<int>Catch;

void moveshark();
void Change(int dir);
void Catching(int r);
void Moving();
void Fishing();


int main()
{
	
	cin >> R >> C >> M;

	while (M--)
	{
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		info[r][c].speed = s;
		info[r][c].dir = d;
		info[r][c].size = z;
	}
	/*
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			printf("%3d", info[i][j].speed);
		}
		cout << endl;
	}
	cout << endl;

	

	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			printf("%3d", info[i][j].size);
		}
		cout << endl;
	}
	cout << endl;
	
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			printf("%3d", info[i][j].dir);
		}
		cout << endl;
	}
	cout << endl;

	*/
	Fishing();

	int hap = 0;
	while (!Catch.empty())
	{
		hap += Catch.back();
		//cout << hap << " ";
		Catch.pop_back();
	}
	//cout << endl;
	cout << hap;

	//system("pause");
	return 0;
}


void moveshark()
{
	int dx[] = { -1,1,0,0 };
	int dy[] = { 0,0,1,-1 };

	while (!Q.empty()) {

		int x = Q.front().x; int y = Q.front().y;
		int D = Q.front().dir ;
		int N = Q.front().speed;
		int S = Q.front().size;
		Q.pop();
		//cout << "x" << x << "y" << y << "speed" << N << "dir" << D << "size" << S << endl;
		for (int i = 0; i < N; i++)
		{
			x += dx[D-1];
			y += dy[D-1];
			//cout << "x" << x << "y" << y << "dir: " << D<< endl;
			if (x < 1 || y < 1 || x > R || y > C)
			{
				if (D == 1) D = 2;
				else if (D == 2) D = 1;
				else if (D == 3) D = 4;
				else if (D == 4) D = 3;
				
				x += dx[D-1];
				x += dx[D-1];
				y += dy[D-1];
				y += dy[D-1];
			}
			
		}
		//cout <<  "dir" << D << "size" << S << endl;
		if (info[x][y].size == 0 || info[x][y].size < S) {
			info[x][y].speed = N;
			info[x][y].dir = D;
			info[x][y].size = S;
		}

	}

}
void Catching(int r)
{
	for (int i = 1; i <= R; i++)
	{
		if (info[i][r].size > 0)
		{
			Catch.push_back(info[i][r].size);
			info[i][r].size = 0;
			info[i][r].speed = 0;
			info[i][r].dir = 0;
			break;
		}

	}
	return;
}

void Moving()
{
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			if (info[i][j].speed > 0)
			{
				Q.push({ i,j,info[i][j].speed,info[i][j].dir,info[i][j].size });
				info[i][j].speed = 0;
				info[i][j].dir = 0;
				info[i][j].size = 0;
				//cout << "i" << i << "j" << j << endl;
			}

		}
	}
	moveshark();
	return;
}

void Fishing()
{
	for (int i = 1; i <= C; i++)
	{
		Catching(i);
		//cout << i << "초" << endl;
		Moving();
		//cout << "물고기" << endl;
		/*
		for (int i = 1; i <= R; i++)
		{
			for (int j = 1; j <= C; j++)
			{
				printf("%3d", info[i][j].size);
			}
			cout << endl;
		}
		cout << endl;
		cout << "방향" << endl;
		for (int i = 1; i <= R; i++)
		{
			for (int j = 1; j <= C; j++)
			{
				printf("%3d", info[i][j].dir);
			}
			cout << endl;
		}
		cout << endl;*/
	}
}

ha_ram 4년 전 2

이 문제가 시간초과가 난다는 것은 아마도 상어가 이동할때 하나하나 다 이동시켜서 시간초과가 날 가능성이 큽니다.

예를들어서 5X5 격자판이라고 가정할 때 어떤 상어가 1000의 속력으로 이동한다면 이걸 그대로 구현시키면 1000번의 루프를 돌아야 합니다.

그런데 잘 생각해보면 5X5격자판에서 상어가 8번 이동하면 다시 자기자리, 원래 방향을 가진 상태로 되는것을 알 수 있습니다. 따라서 1000번의 루프를 돌 필요가 없이 1000을 8로 나눈 나머지만큼만 이동해도 됩니다.

이부분을 생각하시고 구현하시면 시간초과가 안날것입니다.

djm03178 4년 전 1

이와 같은 코드를 위한 데이터가 바로 https://www.acmicpc.net/board/view/36843 에서 추가됐습니다.

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

문제

문제

출처

ICPC

시간초과문제!!!

wjavm2 4년 전 0

ha_ram 4년 전 2

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말