[17143번 낚시왕] - C++

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

모듈러 연산을 사용하여 시간초과가 나오지 않게 하는 것이 이 문제의 포인트였다. 크게 두 가지 방법이 있는데,
1) 속력을 입력 받을 때, 모듈러 연산을 통해 불필요한 반복 움직임을 제거한 후 입력을 받고 상어를 움직이는 방법이 있고,
2) 속력은 그대로 입력 받되 움직인 이후의 상어의 위치와 방향을 모듈러 연산으로 구해주는 방법이 있다.

필자는 2번째 방법으로 시간초과를 해결할 수 있었다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans;
int sec;
int man;
int R,C,M;
vector<int> map[101][101];
int dr[] = {0,-1,1,0,0};
int dc[] = {0,0,0,1,-1};

void sharkMove() {

	vector<int> temp[101][101];

	for(int i=1;i<=R;++i) {
		for(int j=1;j<=C;++j) {
			if(map[i][j].size() > 0) {
				int s,d,z;
				int r,c;
				r = i;
				c = j;
				s = map[i][j][0];  //speed
				d = map[i][j][1];  //direction
				z = map[i][j][2];  //size

				int nr = r, nc = c;
				int dist = s;
				if(d==1) {
					if(nr-1 >= s) {
						nr -= s;
					} else {
						dist -= (nr-1);
						nr = 1;

						int oneWay = dist / (R-1);
						if(oneWay % 2 == 0) {
							if(dist % (R-1) == 0) {
								nr = 1;
								d = 1;
							} else {
								nr = 1 + (dist % (R-1));
								d = 2;
							}
						} else {
							if(dist % (R-1) == 0) {
								nr = R;
								d = 2;
							} else {
								nr = R - (dist % (R-1));
								d = 1;
							}
						}
					}
				} else if(d==2) {
					if(R-nr >= s) {
						nr += s;
					} else {
						dist -= (R-nr);
						nr = R;

						int oneWay = dist / (R-1);
						if(oneWay % 2 == 0) {
							if(dist % (R-1) == 0) {
								nr = R;
								d = 2;
							} else {
								nr = R - (dist % (R-1));
								d = 1;
							}
						} else {
							if(dist % (R-1) == 0) {
								nr = 1;
								d = 1;
							} else {
								nr = 1 + (dist % (R-1));
								d = 2;
							}
						}
					}
				} else if(d==3) {
					if(C-nc >= s) {
						nc += s;
					} else {
						dist -= (C-nc);
						nc = C;

						int oneWay = dist / (C-1);
						if(oneWay % 2 == 0) {
							if(dist % (C-1) == 0) {
								nc = C;
								d = 3;
							} else {
								nc = C - (dist % (C-1));
								d = 4;
							}
						} else {
							if(dist % (C-1) == 0) {
								nc = 1;
								d = 4;
							} else {
								nc = 1 + (dist % (C-1));
								d = 3;
							}
						}
					}
				} else if(d==4) {
					if(nc-1 >= s) {
						nc -= s;
					} else {
						dist -= (nc-1);
						nc = 1;

						int oneWay = dist / (C-1);
						if(oneWay % 2 == 0) {
							if(dist % (C-1) == 0) {
								nc = 1;
								d = 4;
							} else {
								nc = 1 + (dist % (C-1));
								d = 3;
							}
						} else {
							if(dist % (C-1) == 0) {
								nc = C;
								d = 3;
							} else {
								nc = C - (dist % (C-1));
								d = 4;
							}
						}
					}
				}

				r = nr;
				c = nc;

				if(temp[r][c].size() > 0) {
					int z2 = temp[r][c][2];
					if(z > z2) {
						temp[r][c].clear();
						vector<int>().swap(temp[r][c]);

						temp[r][c].push_back(s);
						temp[r][c].push_back(d);
						temp[r][c].push_back(z);
					} else {  // z2 > z
						continue;
					}
				} else {
					temp[r][c].push_back(s);
					temp[r][c].push_back(d);
					temp[r][c].push_back(z);
				}
			}
		}
	}

	for(int i=1;i<=R;++i) {
		for(int j=1;j<=C;++j) {
			map[i][j] = temp[i][j];
		}
	}

	return;
}

void sol() {

	man++;
	for(int i=1;i<=R;++i) {
		if(map[i][man].size() > 0) {
			ans += map[i][man][2];  // catch
			map[i][man].clear();
			vector<int>().swap(map[i][man]);
			break;
		}
	}
	sharkMove();

	
	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	scanf("%d%d%d", &R, &C, &M);
	for(int i=0;i<M;++i) {
		int r,c,s,d,z;
		scanf("%d%d%d%d%d", &r,&c,&s,&d,&z);
		map[r][c].push_back(s);
		map[r][c].push_back(d);
		map[r][c].push_back(z);
	}

	while(sec < C) {
		sol();
		sec++;
	}

	printf("%d\n", ans);
	
	return 0;
}

실행 결과