글 읽기 - 낚시왕 예제는 다맞는데 틀렸습니다 라고 나옵니다 ㅠㅠ 지금 한달째보고있네요 ㅠ

karlema 4년 전 0

낚시왕 예제는 다맞는데 틀렸습니다 라고 나옵니다 ㅠㅠ 지금 한달째보고있네요 ㅠ

제가 할수있는 최대한 확인을 다해봤는데 잘안돼네요 알려주시면 또 열심히 고쳐보겠습니다!!

// 낚시왕
// 어렵다
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int n, m, k;
int map[110][110];
int visit[110][110];
int check[110][110];
int max[11000];
int dy[5] = { 0,-1,1,0,0 };
int dx[5] = { 0,0,0,1,-1 };
// n세로 m가로 k 상어의수
typedef struct a
{
	int y; // y축
	int x; // x축
	int spd; // 이동 속도
	int dir; // 방향
	int size; // 상어크기
	int en; // 상어 활성화
}r;

r shark[11000];
int shcnt;
int king;
int sum;
void shark_print()
{
	for (int i = 0; i < shcnt; i++)
	{
		if (shark[i].en == 1)
			printf("%c번째 %d %d %d %d %d\n", i + 'A', shark[i].y, shark[i].x,shark[i].spd , shark[i].dir, shark[i].size);
	}
	
	printf("\n");
}
void right_move()
{
	king++;
}
void get_shark()
{
	//king은 x축
	//
	// y축의최솟값찾기
	int miny = 987654321;
	for (int i = 0; i < shcnt; i++)
	{
		if (shark[i].en == 0) continue;
		if (shark[i].x == king)
		{
			if (miny > shark[i].y)
				miny = shark[i].y;
		}
	}
	//printf("%d\n",miny);
	for (int i = 0; i < shcnt; i++)
	{
		if (shark[i].en == 0) continue;
		if (shark[i].x == king && shark[i].y == miny)
		{
			//printf("%d %d\n", shark[i].y, shark[i].x);
			shark[i].en = 0;
			sum += shark[i].size;
		}
	}
	//printf("%d\n",sum);
	//printf("getshark\n");
	//shark_print();
}
void eat_shark()
{
	int flag = 0;
	for (int i = 0; i < shcnt; i++)
	{
		if (shark[i].en == 0) continue;
		for (int j = i+1; j < shcnt; j++)
		{
			if (shark[j].en == 0) continue;
			if (shark[i].x == shark[j].x && shark[i].y == shark[j].y)
			{
				if (shark[j].size > shark[i].size)
				{
					shark[i].en = 0;
					flag = 1;
					break;
				}
			}
		}
		if (flag == 1)
		{
			flag = 0;
			break;
		}
	}
	//printf("eatshark\n");
	//shark_print();


}
void shark_move()
{
	//shark_print();

	for (int i = 0; i < shcnt; i++)
	{
		if (shark[i].en == 0) continue;
		for (int j = 1; j <= shark[i].spd; j++)
		{

			int ny = dy[shark[i].dir] + shark[i].y;
			int nx = dx[shark[i].dir] + shark[i].x;

			if (ny<1 || nx<1 || ny>n || nx>m)
			{
				if (shark[i].dir == 1)
				{//위
					shark[i].dir = 2;
				}
				else if (shark[i].dir == 2)
				{//아래
					shark[i].dir = 1;
				}
				else if (shark[i].dir == 3)
				{//오른
					shark[i].dir = 4;
				}
				else if (shark[i].dir == 4)
				{//왼
					shark[i].dir = 3;
				}
				ny = dy[shark[i].dir] + shark[i].y;
				nx = dx[shark[i].dir] + shark[i].x;
			}

			shark[i].y = ny;
			shark[i].x = nx;
			//printf("%d %d %d\n",ny,nx,shark[i].dir);

		}

	}
	//shark_print();

}

void shark_move_3()
{
	//shark_print();

	for (int i = 0; i < shcnt; i++)
	{
		if (shark[i].en == 0) continue;
		for (int j = 1; j <= shark[i].spd; j++)
		{

			int ny = dy[shark[i].dir] + shark[i].y;
			int nx = dx[shark[i].dir] + shark[i].x;

			if (ny<1 || nx<1 || ny>n || nx>m)
			{
				if (shark[i].dir == 1)
				{//위
					shark[i].dir +=1;
				}
				else if (shark[i].dir == 2)
				{//아래
					shark[i].dir -= 1;
				}
				else if (shark[i].dir == 3)
				{//오른
					shark[i].dir +=1;
				}
				else if (shark[i].dir == 4)
				{//왼
					shark[i].dir -= 1;
				}
				ny = dy[shark[i].dir] + shark[i].y;
				nx = dx[shark[i].dir] + shark[i].x;
			}

			shark[i].y = ny;
			shark[i].x = nx;
			//printf("%d %d %d\n",ny,nx,shark[i].dir);

		}

	}
	//shark_print();

}


void shark_move_2()
{
	//shark_print();

	for (int i = 0; i < shcnt; i++)
	{
		if (shark[i].en == 0) continue;
		if (shark[i].dir == 1 || shark[i].dir == 2)
		{
			// y축 방향
			int Rotate = (n - 1) * 2;
			int Speed = shark[i].spd;
			if (Speed >= Rotate) Speed = Speed % Rotate;
			for (int j = 1; j <= Speed; j++)
			{

				int ny = dy[shark[i].dir] + shark[i].y;
				int nx = dx[shark[i].dir] + shark[i].x;

				if (ny<1 || nx<1 || ny>n || nx>m)
				{
					if (shark[i].dir == 1)
					{//위
						shark[i].dir +=1;
					}
					else if (shark[i].dir == 2)
					{//아래
						shark[i].dir -= 1;
					}
					ny = dy[shark[i].dir] + shark[i].y;
					nx = dx[shark[i].dir] + shark[i].x;
					//j--;
				}

				shark[i].y = ny;
				shark[i].x = nx;
				//printf("%d %d %d\n",ny,nx,shark[i].dir);
				
			}
		}
		else
		{
			// x축 방향
			int Rotate = (m - 1) * 2;
			int Speed = shark[i].spd;
			if (Speed >= Rotate) Speed = Speed % Rotate;
			for (int j = 1; j <= Speed; j++)
			{

				int ny = dy[shark[i].dir] + shark[i].y;
				int nx = dx[shark[i].dir] + shark[i].x;

				if (ny<1 || nx<1 || ny>n || nx>m)
				{
					if (shark[i].dir == 3)
					{//오른
						shark[i].dir += 1;
					}
					else if (shark[i].dir == 4)
					{//왼
						shark[i].dir -= 1;
					}
					ny = dy[shark[i].dir] + shark[i].y;
					nx = dx[shark[i].dir] + shark[i].x;
					//j--;
				}

				shark[i].y = ny;
				shark[i].x = nx;
				//printf("%d %d %d\n",ny,nx,shark[i].dir);
			}
		}
	}
	

}
int main()
{
	scanf("%d %d %d", &n, &m, &k);
	if (k == 0)
	{
		printf("0");
		return 0;
	}
	for (int i = 0; i < k; i++)
	{
		int r, c, s, d, z;
		scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
		shark[shcnt].y = r;
		shark[shcnt].x = c;
		shark[shcnt].spd = s;
		shark[shcnt].dir = d;
		shark[shcnt].size = z;
		shark[shcnt].en = 1;
		shcnt++;
	}
	// 가로(m) 축만큼 이동
	for (int i = 0; i < m; i++)
	{
		//1. 낚시왕 오른쪽이동 right_move()
		//2. 가까운 상어 잡음  get_shark()
		//3. 상어가 이동 shark_move()
		//4. 상어 먹기 eat_shark();
		right_move();
		get_shark();
		//shark_move_3();
		shark_move_2();
		eat_shark();
	}
	printf("%d", sum);
	return 0;
}

lovinix 4년 전 0

eat_shark 로직이 이상합니다. 왜 지금 보고있는 상어가 다른 상어에게 잡아먹히면 전체 로직을 종료하시나요?

이걸 고치면 답은 나오긴하는데 제출하면 시간초과가 날것같아 제출해보니 역시 시간초과가 납니다.

상어의 최대 개수가 1만개인데 이걸 n^2 방식으로 열의 개수번만큼 확인해야하니 O(C*K^2) 으로 시간초과가 날 수밖에 없어요

karlema 4년 전 0

아에 새로 설계해서 풀었습니다 감사합니다.

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

문제

문제

출처

ICPC

낚시왕 예제는 다맞는데 틀렸습니다 라고 나옵니다 ㅠㅠ 지금 한달째보고있네요 ㅠ

karlema 4년 전 0

lovinix 4년 전 0

karlema 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말