[백준] 17143번 낚시왕

17143번: 낚시왕

재귀 호출로 상어를 이동시켰다가 시간 초과 걸려서

수학적 계산으로 풀었다.

B 상어를 예로 들어

화살표 길이 = 현재 위치에서 끝까지 갈 때 걸리는 속력 이라 할 때

 

속력 ≤ 화살표 길이

일 때는 현재 방향 그대로 한 번에 이동이 가능하지만

 

속력(5) > 화살표 길이(3)

일 때는 방향을 바꿔 왔다 갔다 해야 하므로

왕복 횟수 : (속력 - 화살표 길이) / 총 길이

왕복 후 남은 속력 : (속력 - 화살표 길이) % 총 길이

를 구해준다.

 

이때 총 길이 = 상어가 처음부터 끝까지 가는데 걸리는 속력 이므로

상어의 방향이 ↑↓일 땐 R-1,

→←일 땐 C-1이다.

그림은 왕복 횟수가 2 / 3 = 0회 이고,

왕복이 끝난 후 남은 속력은 2 % 3 = 2이다.

초반에 끝까지 1번 이동 + 왕복 0번 = 1은 홀수이므로 방향을 바꾼다.

쉽게 말해서 왕복 횟수가 짝수면 방향을 반대로 바꿔야 한다.

 

그러면 이 상태가 된다.

현재 방향대로 남은 속력만큼 이동해야 하므로

방향에 알맞은 위치에 상어를 위치시킨 모습이다.

(↑ : 열의 끝, ↓ : 열의 처음, → : 행의 처음, ← : 행의 끝)

 

이대로 속력만큼 이동한 위치가 현재 상어의 새 위치가 되고

그 위치에 상어가 이미 있다면 크기가 더 큰 상어를 저장한다.

#include <iostream>
#include <vector>
using namespace std;
int R, C, M, r, c, s, d, z, res, X, Y, S, D, val, len;
int dx[5] = { 0, -1, 1, 0, 0 }, dy[5] = { 0, 0, 0, 1, -1 }, dd[5] = { 0, 2, 1, 4, 3 };
class Shark {
public:
	int speed, direction, size;
	Shark(int speed, int direction, int size) {
		this->speed = speed;
		this->direction = direction;
		this->size = size;
	}
};
vector<Shark> v[102][102];
int main() {
	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
		cin >> r >> c >> s >> d >> z;
		v[r][c].push_back(Shark(s, d, z));
	}
	for (int t = 1; t <= C; t++) { //상어 낚시
		for (int i = 1; i <= R; i++) {
			if (!v[i][t].empty()) {
				res += v[i][t][0].size;
				v[i][t].clear();
				break;
			}
		}
		vector<Shark> tmp[102][102];
		for (int i = 1; i <= R; i++) { //상어 이동
			for (int j = 1; j <= C; j++) {
				if (v[i][j].empty()) continue;
				D = v[i][j][0].direction, S = v[i][j][0].speed;
				if (D == 1) val = i - 1, len = R - 1;
				else if (D == 2) val = R - i, len = R - 1;
				else if (D == 3) val = C - j, len = C - 1;
				else val = j - 1, len = C - 1;

				if (S <= val) X = i + dx[D] * S, Y = j + dy[D] * S; //한번에 이동이 가능할 때
				else { //왔다갔다 거려야할 때
					if (!(((S - val) / len) % 2)) D = dd[D];
					if (D == 1) X = R, Y = j;
					else if (D == 2) X = 1, Y = j;
					else if (D == 3) X = i, Y = 1;
					else X = i, Y = C;
					X += dx[D] * ((S - val) % len), Y += dy[D] * ((S - val) % len);
				}

				if (tmp[X][Y].empty() || tmp[X][Y][0].size < v[i][j][0].size) {
					tmp[X][Y].clear();
					tmp[X][Y].push_back(Shark(S, D, v[i][j][0].size));
				}
				v[i][j].clear();
			}
		}
		for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) if (!tmp[i][j].empty()) v[i][j].push_back(Shark(tmp[i][j][0].speed, tmp[i][j][0].direction, tmp[i][j][0].size));
	}
	cout << res;
	return 0;
}