글 읽기 - 낚시왕 시간초과 관련 질문 있습니다.

skekq123 3년 전 0

문제는 해결했지만, 두 코드간에 어떤 차이인지 잘 모르겠어서 질문 드립니다.

문제는

for(y제어)

{

낚시function

상어움직임 function

}

식으로 풀었습니다.

shark_move 함수에서 상어를 움직이는 좌표 방식이 1과 2방식이 조금 다른데, 어떤 차이때문에 1번코드가 시간초과가 나는지 모르겠습니다.

/////////////시간초과 코드 1번
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#define max_n 100
using namespace std;

typedef struct
{
	int speed, move, size;
}shark;

int dx[5] = { 0,-1,1,0,0 };
int dy[5] = { 0,0,0,1,-1 };
shark map[max_n + 1][max_n + 1];
shark empty_shark = { 0,0,0 };
shark moved_map[max_n + 1][max_n + 1];
int n, m;
int shark_cnt;
int ans;
void input();
int get_next_move(int cur_move);
void shark_move();
void solution();
void duplicate();
void fishing(int cur_y);
void print();
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	input();
	solution();
	cout << ans << '\n';

	return 0;
}
void solution()
{
	for (int i = 1; i <= m; ++i) // 낚시꾼 움직이는 for문 
	{
		fishing(i);
		shark_move(); // 움직이고나서
		duplicate();
	}
}
void fishing(int cur_y)
{
	for (int j = 1; j <= n; ++j) // 행
	{
		if (map[j][cur_y].size != 0)
		{
			ans += map[j][cur_y].size;
			map[j][cur_y] = empty_shark;
			break;
		}
	}
}
void duplicate()
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			map[i][j] = moved_map[i][j];
			moved_map[i][j] = empty_shark;
		}
	}
}
void shark_move()
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (map[i][j].size == 0) continue;
			int cur_speed = map[i][j].speed;
			int cur_move = map[i][j].move;
			int cur_size = map[i][j].size;
			int nx = i;
			int ny = j;
			for (int t = 0; t < cur_speed; ++t)
			{
				nx += dx[cur_move];
				ny += dy[cur_move];
				if (nx < 1 || ny < 1 || nx > n || ny > m) // 범위 초과했으면, 역방향으로 한칸 간거니까 반대로 2번가주기
				{
					cur_move = get_next_move(cur_move);
					nx += dx[cur_move];
					ny += dy[cur_move];
					nx += dx[cur_move];
					ny += dy[cur_move];
				}
			}
			if (moved_map[nx][ny].size > cur_size) continue;
			shark temp;
			temp.speed = cur_speed;
			temp.size = cur_size;
			temp.move = cur_move;
			moved_map[nx][ny] = temp;
		}
	}
}
int get_next_move(int cur_move)
{
	if (cur_move == 1) return 2;
	else if (cur_move == 2) return 1;
	else if (cur_move == 3) return 4;
	else return 3;
}
void input()
{
	cin >> n >> m >> shark_cnt;
	for (int i = 1; i <= shark_cnt; ++i)
	{
		int x, y, speed, move, size;
		cin >> x >> y >> speed >> move >> size;
		shark temp;
		temp.speed = speed;
		temp.move = move;
		temp.size = size;
		map[x][y] = temp;
	}
}


/////////////////////////////////////// 해결코드 2번

#include<iostream>
#include<algorithm>
#define max_n 100
using namespace std;

typedef struct
{
	int speed, move, size;
}shark;

int dx[5] = { 0,-1,1,0,0 };
int dy[5] = { 0,0,0,1,-1 };
shark map[max_n + 1][max_n + 1];
shark empty_shark = { 0,0,0 };
shark moved_map[max_n + 1][max_n + 1];
int n, m;
int shark_cnt;
int ans;
void input();
int get_next_move(int cur_move);
void shark_move();
void solution();
void duplicate();
void fishing(int cur_y);
void print();
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	input();
	solution();
	cout << ans << '\n';

	return 0;
}
void solution()
{
	for (int i = 1; i <= m; ++i) // 낚시꾼 움직이는 for문 
	{
		fishing(i);
		shark_move(); // 움직이고나서
		duplicate();
	}
}
void fishing(int cur_y)
{
	for (int j = 1; j <= n; ++j) // 행
	{
		if (map[j][cur_y].size != 0)
		{
			ans += map[j][cur_y].size;
			map[j][cur_y] = empty_shark;
			break;
		}
	}
}
void duplicate()
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			map[i][j] = moved_map[i][j];
			moved_map[i][j] = empty_shark;
		}
	}
}
void shark_move()
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (map[i][j].size == 0) continue;
			int cur_speed = map[i][j].speed;
			int cur_move = map[i][j].move;
			int cur_size = map[i][j].size;
			int nx = i;
			int ny = j;
			for (int t = 0; t < cur_speed; ++t)
			{
				if (nx == 1 && cur_move == 1) cur_move = 2;
				if (nx == n && cur_move == 2) cur_move = 1;
				if (ny == 1 && cur_move == 4) cur_move = 3;
				if (ny == m && cur_move == 3) cur_move = 4;
				switch (cur_move)
				{
				case 1: --nx;
					break;
				case 2: ++nx;
					break;
				case 3: ++ny;
					break;
				case 4: --ny;
					break;
				}
			}
			if (moved_map[nx][ny].size > cur_size) continue;
			shark temp;
			temp.speed = cur_speed;
			temp.size = cur_size;
			temp.move = cur_move;
			moved_map[nx][ny] = temp;
		}
	}
}
int get_next_move(int cur_move)
{
	if (cur_move == 1) return 2;
	else if (cur_move == 2) return 1;
	else if (cur_move == 3) return 4;
	else return 3;
}
void input()
{
	cin >> n >> m >> shark_cnt;
	for (int i = 1; i <= shark_cnt; ++i)
	{
		int x, y, speed, move, size;
		cin >> x >> y >> speed >> move >> size;
		shark temp;
		temp.speed = speed;
		temp.move = move;
		temp.size = size;
		map[x][y] = temp;
	}
}

pichulia 3년 전 1

아니 이게 왜 통과되죠...

원래라면 둘다 시간초과가 나야합니다..

skekq123 3년 전 0

감사합니다 덕분에, 애초에 잘못된걸 알고 speed를 하나하나 움직이는 방식이 아닌

제자리로 오는 특정 speed 값을 구하고, 이 값으로 나눈 나머지만큼만 움직이니 시간이 확 줄었네요

mywoospam 1년 전 0

skekq123님 덕분에 시간 초과 해결했습니다

감사합니다

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

문제

문제

출처

ICPC

낚시왕 시간초과 관련 질문 있습니다.

skekq123 3년 전 0

pichulia 3년 전 1

skekq123 3년 전 0

mywoospam 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말