글 읽기 - 낚시왕 '시간초과' ..어디가 잘못된걸까요ㅠㅠ?

jasaeong93 4년 전 0

모두 정확한 정답이 나오는데 제출만 하면 시간초과가 나오네요 어디가 잘못된걸까요?

아직 제가 코딩이 익숙하지 않아서 코드가 읽기 어렵지만, 시간내어 읽어주시고 문제점이 혹시나 보인다면 답글 부탁드립니다!

감사합니다!

#include <iostream>
#include <vector>
using namespace std;
#define MAX 102

int dRow[] = { 0,-1,1,0,0 };
int dCol[] = { 0, 0,0,1,-1 };
int R, C, M;
int cnt;

typedef struct
{
	int row; 
	int col;
	int speed;
	int dir;
	int size;
	bool live;
}FISH;

FISH* map[MAX][MAX];
vector<FISH> vecFish;

void Fishing(int col)
{
	for (int i = 1; i <= R; i++)
	{
		if (map[i][col] != NULL)
		{
			cnt += map[i][col]->size;
			map[i][col]->live = false;
			map[i][col] = NULL;
			break;
		}
	}
}

void move(FISH* node)
{
	//좌표 확인 
	for (int i = 0; i < node->speed; i++)
	{
		if (node->row == 1 && node->dir == 1)

		{
			node->dir = 2;
			node->row += dRow[node->dir];
		}
		else if (node->row == R && node->dir == 2)
		{
			node->dir = 1;
			node->row += dRow[node->dir];
		}
		else if (node->col == 1 && node->dir == 4)
		{
			node->dir = 3;
			node->col += dCol[node->dir];
		}
		else if (node->col == C && node->dir == 3)
		{
			node->dir = 4;
			node->col += dCol[node->dir];
		}
		else
		{
			node->row += dRow[node->dir];
			node->col += dCol[node->dir];
		}
	}

	//중복 체크 
	if (map[node->row][node->col] == NULL)
	{
		map[node->row][node->col] = node;
	}

	else
	{
		if (node->size > map[node->row][node->col]->size)
		{
			map[node->row][node->col]->live = false;
			map[node->row][node->col] = node;
		}
		else
		{
			node->live = false;
		}
	}
}
void update_map()
{
	//map clear
	for (int i = 0; i < vecFish.size(); i++)
	{
		if (vecFish[i].live == false) continue;
		int row = vecFish[i].row;
		int col = vecFish[i].col;
		map[row][col] = NULL;
	}

	//map update
	for (int i = 0; i < vecFish.size(); i++)
	{
		if (vecFish[i].live == true)
		{
			move(&vecFish[i]);
		}
	}
}


int main()
{
	int r, c, s, d, z;
	cin >> R >> C >> M;



	for (int i = 0; i < M; i++)
	{
		//r,c,s,d,z

		cin >> r >> c >> s >> d >> z;
		FISH fish = { r, c, s, d, z, true };
		vecFish.push_back(fish);
	}

	for (int i = 0; i < vecFish.size(); i++)
	{
		map[vecFish[i].row][vecFish[i].col] = &vecFish[i];
	}

	/*for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
			cout << map[i][j]->row << " ";

		cout << endl;
	}*/

	for (int i = 1; i <= C; i++)
	{
		Fishing(i);
		update_map();
	}
	cout << cnt << endl;
}

whwjdrms 4년 전 1

update_map함수에서 각각 상어의 스피드만큼 for문을 돌리므로 상어 최대수:10000*상어 최대 스피드:1000인데 거기에 141번째줄 C만큼 for문을 더돌리셔서 연산횟수가 10^9이 되어버려 시간초과가 나는 듯 합니다. move함수 알고리즘을 다시 한번 생각해보시는 게 좋을 듯합니다

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

문제

문제

출처

ICPC

낚시왕 '시간초과' ..어디가 잘못된걸까요ㅠㅠ?

jasaeong93 4년 전 0

whwjdrms 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말