글 읽기 - 시간초과 질문드립니다.

semo_semo 4년 전 0

문제를 해결하는 도중에 계속 시간초과가 발생해서 질문 드립니다.

질문 내용들을 확인해보니 move를 하는 횟수가 너무 많아지면 불필요한 반복문이 돌아가 시간초과가 뜬다는 말이 있길래, 규칙을 찾아 %연산을 통해 move횟수를 최대한 줄여서 실행했는데도 시간초과가 떠서 질문드립니다.

도와주세요ㅜ

#include <iostream>

using namespace std;

struct SHARK {
	int r, c, s, d, z;
};

int r, c, m;
SHARK map[101][101] = { 0, };
SHARK shark[10000];

int fisher_pos = 0;				//낚시꾼 위치
int ans = 0;
void catch_shark() {
	int shark_idx = -1;
	int min_row = 101;
	/* 낚시꾼이 잡을 상어의 인덱스를 받아온다. */
	for (int i = 0; i < m; i++) {
		if (shark[i].c == fisher_pos) {
			if (shark[i].r < min_row) {
				min_row = shark[i].r;
				shark_idx = i;
			}
		}
	}
	if (shark_idx != -1) {
		ans += shark[shark_idx].z;		//잡은 상어의 크기만큼 ans에 더해준다.
		shark[shark_idx].r = 0, shark[shark_idx].c = 0, shark[shark_idx].s = 0, shark[shark_idx].d = 0, shark[shark_idx].z = 0;		//잡힌 상어는 모든 값을 0으로 초기화, 즉 1 <= r, c <= 100 인 격자판에서 빼줬다고 생각.
	}
}

void move_shark() {
	int move_cnt;
	for (int i = 0; i < m; i++) {
		if (shark[i].r == 0 && shark[i].c == 0) {		//잡아먹힌 상어에 대해서.
			continue;
		}
		
		move_cnt = shark[i].s;
		/* 위 아래 */
		if (shark[i].d == 1 || shark[i].d == 2) {
			move_cnt %= ((r - 1) * 2);
			while (move_cnt != 0) {
				if (shark[i].r == 1 && shark[i].d == 1) {
					shark[i].d = 2;
				}
				else if (shark[i].r == r && shark[i].d == 2) {
					shark[i].d = 1;
				}

				--move_cnt;
				if (shark[i].d == 1) {
					shark[i].r -= 1;
				}
				else if (shark[i].d == 2) {
					shark[i].r += 1;
				}
			}
		}

		/* 오른쪽 왼쪽 */
		if (shark[i].d == 3 || shark[i].d == 4) {
			move_cnt %= ((c - 1) * 2);
			while (move_cnt != 0) {
				if (shark[i].c == 1 && shark[i].d == 4) {
					shark[i].d = 3;
				}
				else if (shark[i].c == c && shark[i].d == 3) {
					shark[i].d = 4;
				}

				--move_cnt;
				if (shark[i].d == 3) {
					shark[i].c += 1;
				}
				else if (shark[i].d == 4) {
					shark[i].c -= 1;
				}
			}
		}
	}

	/* 상어 위치들 비교해 가면서 같은 위치에 있을 경우 상어 사이즈를 비교해서 상어를 먹는 부분 구현 */
	for (int i = 0; i < m - 1; i++) {
		for (int j = i + 1; j < m; j++) {
			if (shark[j].r == 0 && shark[j].c == 0) {
				continue;
			}
			if ((shark[i].r == shark[j].r) && (shark[i].c == shark[j].c)) {
				if (shark[i].z > shark[j].z) {
					shark[j].r = 0, shark[j].c = 0, shark[j].s = 0, shark[j].d = 0, shark[j].z = 0;
				}
				else {
					shark[i].r = 0, shark[i].c = 0, shark[i].s = 0, shark[i].d = 0, shark[i].z = 0;
					break;
				}
			}
		}
	}
}

int main()
{
	scanf("%d %d %d", &r, &c, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d %d %d", &shark[i].r, &shark[i].c, &shark[i].s, &shark[i].d, &shark[i].z);
		map[shark[i].r][shark[i].c] = shark[i];
	}
	
	for (int x = 1; x <= c; x++) {		//매 초 마다 일어나야 할 행동
		/* TODO */
		// 낚시꾼 오른쪽으로 한칸 이동
		++fisher_pos;

		// 낚시꾼이 위치한 열의 상어중 가장 가까운 상어(r값이 가장 작은 물고기) 잡기
		catch_shark();

		// moving shark
		move_shark();
	}

	printf("%d\n", ans);

	return 0;
}

semo_semo 4년 전 0

같은 위치에 상어가 있을 때 상어가 서로를 먹는 과정에서 너무 많은 반복문이 도는 것 같아 다음과 같이 수정해주어서 10%까지는 가는데 10%에서 시간초과가 뜹니다ㅜ.

조언 부탁드리겠습니다ㅜ.

#include <iostream>
using namespace std;

struct SHARK {
	int r, c, s, d, z;
};

int r, c, m;
SHARK map[101][101] = { 0, };
SHARK shark[10000];

int fisher_pos = 0;				//낚시꾼 위치
int ans = 0;
void catch_shark() {
	int shark_idx = -1;
	int min_row = 101;
	/* 낚시꾼이 잡을 상어의 인덱스를 받아온다. */
	for (int i = 0; i < m; i++) {
		if (shark[i].c == fisher_pos) {
			if (shark[i].r < min_row) {
				min_row = shark[i].r;
				shark_idx = i;
			}
		}
	}
	if (shark_idx != -1) {
		ans += shark[shark_idx].z;		//잡은 상어의 크기만큼 ans에 더해준다.
		shark[shark_idx].r = 0, shark[shark_idx].c = 0, shark[shark_idx].s = 0, shark[shark_idx].d = 0, shark[shark_idx].z = 0;		//잡힌 상어는 모든 값을 0으로 초기화, 즉 1 <= r, c <= 100 인 격자판에서 빼줬다고 생각.
	}
}

void move_shark() {
	SHARK updatemap[101][101] = { 0, };
	int move_cnt;
	for (int i = 0; i < m; i++) {
		if (shark[i].r == 0 && shark[i].c == 0) {		//잡아먹힌 상어에 대해서.
			continue;
		}
		
		move_cnt = shark[i].s;
		/* 위 아래 */
		if (shark[i].d == 1 || shark[i].d == 2) {
			move_cnt %= ((r - 1) * 2);
			while (move_cnt != 0) {
				if (shark[i].r == 1 && shark[i].d == 1) {
					shark[i].d = 2;
				}
				else if (shark[i].r == r && shark[i].d == 2) {
					shark[i].d = 1;
				}

				--move_cnt;
				if (shark[i].d == 1) {
					shark[i].r -= 1;
				}
				else if (shark[i].d == 2) {
					shark[i].r += 1;
				}
			}
		}

		/* 오른쪽 왼쪽 */
		if (shark[i].d == 3 || shark[i].d == 4) {
			move_cnt %= ((c - 1) * 2);
			while (move_cnt != 0) {
				if (shark[i].c == 1 && shark[i].d == 4) {
					shark[i].d = 3;
				}
				else if (shark[i].c == c && shark[i].d == 3) {
					shark[i].d = 4;
				}

				--move_cnt;
				if (shark[i].d == 3) {
					shark[i].c += 1;
				}
				else if (shark[i].d == 4) {
					shark[i].c -= 1;
				}
			}
		}
		
		/* 상어 위치들 비교해 가면서 같은 위치에 있을 경우 상어 사이즈를 비교해서 상어를 먹는 부분 구현 */
		for (int j = i - 1; j >= 0; j--) {
			if (shark[i].r == shark[j].r && shark[i].c == shark[j].c) {
				if (shark[i].z > shark[j].z) {
					shark[j].r = 0, shark[j].c = 0, shark[j].s = 0, shark[j].d = 0, shark[j].z = 0;
				}
				else {
					shark[i].r = 0, shark[i].c = 0, shark[i].s = 0, shark[i].d = 0, shark[i].z = 0;
					break;
				}
			}
		}
	}
	



	/* 상어 위치들 비교해 가면서 같은 위치에 있을 경우 상어 사이즈를 비교해서 상어를 먹는 부분 구현 */
	/*for (int i = 0; i < m - 1; i++) {
		for (int j = i + 1; j < m; j++) {
			if (shark[j].r == 0 && shark[j].c == 0) {
				continue;
			}
			if ((shark[i].r == shark[j].r) && (shark[i].c == shark[j].c)) {
				if (shark[i].z > shark[j].z) {
					shark[j].r = 0, shark[j].c = 0, shark[j].s = 0, shark[j].d = 0, shark[j].z = 0;
				}
				else {
					shark[i].r = 0, shark[i].c = 0, shark[i].s = 0, shark[i].d = 0, shark[i].z = 0;
					break;
				}
			}
		}
	}*/
}

int main()
{
	scanf("%d %d %d", &r, &c, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d %d %d", &shark[i].r, &shark[i].c, &shark[i].s, &shark[i].d, &shark[i].z);
		map[shark[i].r][shark[i].c] = shark[i];
	}
	
	for (int x = 1; x <= c; x++) {		//매 초 마다 일어나야 할 행동
		/* TODO */
		// 낚시꾼 오른쪽으로 한칸 이동
		++fisher_pos;

		// 낚시꾼이 위치한 열의 상어중 가장 가까운 상어(r값이 가장 작은 물고기) 잡기
		catch_shark();

		// moving shark
		move_shark();
	}

	printf("%d\n", ans);

	return 0;
}

semo_semo 4년 전 0

해결했습니다. 상어 먹는 부분을 for문을 없애고 해결하려고 하니 해결되었습니다.

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

semo_semo 4년 전 0

semo_semo 4년 전 0

semo_semo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말