낚시왕 (feat. 백준, 17143번)

낚시왕
https://www.acmicpc.net/problem/17143

17143번: 낚시왕

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/17143
#include <iostream>

using namespace std;

struct Shark {
	int s, d, z;	// 속도, 이동방향, 크기
	bool exist;
};

int R, C, M;
int dx[4], dy[4];
Shark maps[101][101];
Shark tmp[101][101];

inline void fishing(int& result, int& iy)
{
	for (auto ix = 1; ix <= R; ++ix)
		if (maps[ix][iy].exist) {
			result += maps[ix][iy].z; maps[ix][iy].exist = false;
			break;
		}
}

inline void moving()
{
	for(int ix = 1, iy, x, y, s, idx, nx, ny; ix <= R; ++ix)
		for(iy = 1; iy <= C; ++iy)
			if (maps[ix][iy].exist)
			{
				maps[ix][iy].exist = false;
				x = ix, y = iy;
				s = maps[ix][iy].s;
				/* 위 아래 */
				if (maps[ix][iy].d == 1 || maps[ix][iy].d == 2)
					s %= ((R - 1) * 2);
				/* 오른쪽 왼쪽 */
				if (maps[ix][iy].d == 3 || maps[ix][iy].d == 4)
					s %= ((C - 1) * 2);
				for (idx = 0; idx < s; ++idx)
				{
					nx = x + dx[maps[ix][iy].d - 1];
					ny = y + dy[maps[ix][iy].d - 1];
					if (1 <= nx && nx <= R && 1 <= ny && ny <= C)
						x = nx, y = ny;
					else {
						if (maps[ix][iy].d == 1)			maps[ix][iy].d = 2;
						else if (maps[ix][iy].d == 2)		maps[ix][iy].d = 1;
						else if (maps[ix][iy].d == 3)		maps[ix][iy].d = 4;
						else								maps[ix][iy].d = 3;
						--idx;
					}
				}

				if (!tmp[x][y].exist)
					tmp[x][y] = maps[ix][iy], tmp[x][y].exist = true;
				else {
					auto& shark = tmp[x][y];
					if (shark.z < maps[ix][iy].z)
						tmp[x][y] = maps[ix][iy], tmp[x][y].exist = true;
				}
			}
	for (int ix = 1, iy; ix <= R; ++ix)
		for (iy = 1; iy <= C; ++iy) {
			if (tmp[ix][iy].exist)
				maps[ix][iy] = tmp[ix][iy], tmp[ix][iy].exist = false;
		}
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();

	cin >> R >> C >> M;
	dx[0] = -1, dx[1] = 1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	for (int ix = 1, iy; ix <= R; ++ix)
		for (iy = 1; iy <= C; ++iy)
			maps[ix][iy].exist = false, tmp[ix][iy].exist = false;

	for (int idx = 0, r, c, s, d, z; idx < M; ++idx)
		cin >> r >> c >> s >> d >> z, maps[r][c].s = s, maps[r][c].d = d, maps[r][c].z = z, maps[r][c].exist = true;

	auto result = 0;
	for (auto iy = 1; iy <= C; ++iy)
	{
		fishing(result, iy);
		moving();
	}
	cout << result << endl;

	return 0;
}
// *&)*@*

1. 구현상의 어려움을 없을거라고 봅니다.
2. 핵심은 상어의 속도만큼 한칸씩 이동할 것인가 입니다. (이 부분에서 시간초과가 발생합니다.)
3. 상어의 속도가 굉장히 큰값이더라도 이동할 수 있는 범위는 R/C 내에서 가능하므로, (R/C-1) * 2의 나머지만큼만 움직입니다.
4. 여기서 저는 나머지만큼에 대해서 한칸씩 반복문을 수행하였지만, 한번에 여러칸을 움직이도록 하면 더 빠른 시간의 결과를 얻을 수 있습니다.