acmicpc17143.md

낚시왕

[https://www.acmicpc.net/problem/17143]

개요

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.

3. 상어가 이동한다.

4. 낚시왕이 끝 열(2<=R,C<=100)에 도달하였을 때 잡은 상어 크기(z)의 합을 구하면 된다.

상어(0<= 상어의 수=M <=10000)의 이동은 입력에서 주어진 방향(d)과 속도(0 <= s <= 1000)로 이동하고 끝에 다다르면 반대 방향으로 이동하기 시작한다. 상어의 이동 후 같은 칸(r,c)에 상어가 두 마리 이상있다면 크기(z)가 큰 상어가 모두 잡아먹는다. (r, c, s, d, z)의 순서로 주어진다.

분석

시간복잡도

낚시왕이 이동하는 횟수가 열의 개수 C(100)이고 상어의 수가 M(10000)이다. 상어 한마리당 이동하는 칸수는 s(1000)이므로 단순히 한 칸씩이동을 시킨다면 100*10000*1000=10억으로 시간초과가 나게 된다. 따라서 좌표를 직접 계산하여 구하는 방법과 mod 연산으로 s를 줄여서 시뮬레이션하는 방법을 이용하면 시간 내에 이동시킬 수 있다.

상어를 한 칸씩 이동시키다보면 s와 R, C(행, 열 너비)에 따라 규칙성을 찾을 수 있다. 찾은 규칙은 (R,C -1)*2 번 이동할 때마다 상어의 위치와 방향이 반복된다는 것이다. 따라서 이를 이용하여 좌표를 계산할 수도 있고 mod연산을 통하여 시간을 줄일 수 있다.

또한 상어가 상어를 잡아먹는 경우 chi(map형태의 배열)에 크기의 최댓값을 저장해놓고 상어를 탐색하며 map의 최댓값과 크기가 같은 상어들만 살리면 상어의 수만큼 탐색할 수 있다.

알고리즘

1. 열(C) 수 만큼 반복한다.
   1. 1부터 R까지 탐색하며 상어를 찾으면 좌표 저장 후 종료한다.
   2. 1부터 상어의 수만큼 반복한다.
      1. 좌표비교를 통하여 낚시왕이 잡은 상어가 맞다면 죽이면서 answer에 크기를 더한다.
      2. 그렇지 않다면 상어를 이동시키며 map에 체크한다.(map에 상어의 수가 들어가 있도록)
   3. 1부터 상어의 수만큼 반복하며 chi[r][c]에 상어의 최대 크기를 저장한다.
   4. 1부터 상어의 수만큼 반복하며 chi[r][c]와 크기가 같은 상어만을 살린다.
2. answer 출력

소스

#include <stdio.h>

int map[110][110], chi[110][110], sang[10010][6], bang[5][2] = { {0,0}, {-1, 0},{1,0}, {0,1}, {0,-1} }, cha[5] = { 0, 2, 1, 4, 3 };

int main()
{
	int i, j, k, r, c, n, answer = 0, nr, nc, d, s, er, ec, ac;
	scanf("%d%d%d", &r, &c, &n);
	for (i = 1; i <= r; i++)
	{
		for (j = 1; j <= c; j++)
		{
			map[i][j] = 0;
			chi[i][j] = 0;
		}
	}
	for (i = 1; i <= n; i++)
	{
		for (j = 0; j < 5; j++) scanf("%d", &sang[i][j]);
		sang[i][5] = 0;
		map[sang[i][0]][sang[i][1]]++;
	}
	for (k = 1; k <= c; k++)
	{
		er = 0;
		ec = 0;
		for (i = 1; i <= r; i++)
		{
			if (map[i][k] != 0)
			{
				er = i;
				ec = k;
				break;
			}
		}

		for (i = 1; i <= n; i++)
		{
			nr = sang[i][0];
			nc = sang[i][1];
			s = sang[i][2];
			d = sang[i][3];
			map[nr][nc] --;

			if (er == nr && ec == nc)
			{
				answer += sang[i][4];
				sang[i][5] = 1;
			}
			else
			{
				if (d == 1 || d == 2) s %= ((r - 1) * 2);
				else s %= ((c - 1) * 2);
				while (s > 0)
				{
					s--;
					if ((nr == 1 && d == 1) || (nr == r && d == 2)) d = cha[d];
					if ((nc == 1 && d == 4) || (nc == c && d == 3)) d = cha[d];
					nr += bang[d][0];
					nc += bang[d][1];
				}
				map[nr][nc] ++;
				sang[i][0] = nr;
				sang[i][1] = nc;
				sang[i][3] = d;
			}
		}
		for (i = 1; i <= n; i++)
		{
			nr = sang[i][0];
			nc = sang[i][1];
			if (chi[nr][nc] < sang[i][4] && map[nr][nc]>0 && sang[i][5]==0) chi[nr][nc] = sang[i][4];
		}

		ac = 0;

		for (i = 1; i <= n; i++)
		{
			nr = sang[i][0];
			nc = sang[i][1];
			if (map[nr][nc] > 0 && chi[nr][nc] == sang[i][4] && sang[i][5]==0)
			{
				++ac;
				sang[ac][0] = sang[i][0];
				sang[ac][1] = sang[i][1];
				sang[ac][2] = sang[i][2];
				sang[ac][3] = sang[i][3];
				sang[ac][4] = sang[i][4];
				sang[ac][5] = sang[i][5];
				chi[nr][nc] = 0;
				map[nr][nc] = 1;
			}
		}
		n = ac;
	}
	printf("%d", answer);
}