[ boj : 17143 ] 낚시왕

www.acmicpc.net/problem/17143

17143번: 낚시왕

문제 : 낚시왕은 한칸씩 오른쪽으로 움직이고 그 열에 해당하는 가장 가까운 상어를 잡습니다. 이때 상어는 속력과 방향,크기를 가지고 있고 만약 같은 칸에 동일한 상어가 2마리 이상 겹친다면 크기가 가장 큰 상어가 전부 잡아먹습니다.

이때 낚시왕이 낚시를 끝내고 잡은 상어들의 무게의 합을 구하시오

 

해설 : 

전형적인 삼성 문제라 너무 힘드네요 ㅠㅠㅠㅠㅠㅠㅠ 구현력이 대체 언제 느련지....

가장 중요한 키포인트만 설명하겠습니다. 나머진 ,,,구현력의 문제라서요.

 

일단 매 동작을 실행하면 시간초과가 발생합니다. 속력의 최대가 1000 이고 100x100 의 격자판이기 때문이죠. 또한 여러가지 상수가 더해지면 힘들어 보입니다. 

 

그래서 매 동작을 수행하지 않고 이를 줄여줄 수 있는 방법을 택해야 되는데 

상어가 원래 있던 자리에 같은 방향을 가진채로 돌아오려면 세로 : (R-1)x2 , 가로 : (C-1)x2 의 움직임을 가지면 됩니다.

 

즉, (R-1)x2 ,(C-1)x2 을 상어가 가지고 있는 속력에 나누어 준 나머지 만큼만 이동해도 결국은 매 동작을 수행하는 것과 같아지게 된다는 뜻입니다.

 

주의할점은 에초에 상어가 시작할때 격자판을 벗어날 수 있는 경우가 존재할 수 있으니 방향을 먼저 체크해 주고 난 후에 동작을 가져가주시면 되겠습니다.

 

그리고 크기가 가장 큰 상어만 잡으니 priority_queue 2개를 사용해서 이동하고 복사하고 이 과정을 반복해주었습니다.

 

#include<bits/stdc++.h>

using namespace std;

struct info {
	int s, d, z;
	bool operator<(const info& cur) const {
		return z < cur.z;
	}
};

int R, C, M;
priority_queue<info> pq1[101][101];

void solve();
void move();
void show();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();
	return 0;
}
void solve()
{	
	int r, c, s, d, z;
	cin >> R >> C >> M;

	for (int i = 0; i < M; i++) {
		cin >> r >> c >> s >> d >> z;
		pq1[r-1][c-1].push({ s,d-1,z });
	}

	int ans = 0;
	for (int i = 0; i < C; i++) {
		for (int j = 0; j < R; j++) {
			if (pq1[j][i].size() > 0) {
				ans += pq1[j][i].top().z;
				pq1[j][i].pop();
				break;
			}
		}
		move();
		//show();
	}
	cout << ans;
}
void show()
{
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (pq1[i][j].size() > 0)
				cout << pq1[i][j].top().z << " ";
			else
				cout << 0 << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}
void move()
{
	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,1,-1 };
	priority_queue<info> pq2[101][101];

	for(int i=0;i<R;i++)
		for(int j=0;j<C;j++)
			while (pq1[i][j].size() > 0) {
				info cur = pq1[i][j].top();
				pq1[i][j].pop();
				int tx=i, ty=j;
				
				int step;

				if (cur.d == 0 || cur.d == 1)
					step = cur.s % ((R-1)*2);
				else
					step = cur.s % ((C-1)*2);
				
				for (int k = 0; k < step; k++) {
					switch (cur.d) {
					case 0:
						if (tx == 0)cur.d = 1;
						break;
					case 1:
						if (tx == R - 1)cur.d = 0;
						break;
					case 2:
						if (ty == C - 1)cur.d = 3;
						break;
					case 3:
						if (ty == 0)cur.d = 2;
						break;
					}
					tx += dx[cur.d];
					ty += dy[cur.d];										
				}
				pq2[tx][ty].push(cur);
			}
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if (pq2[i][j].size() > 0)
				pq1[i][j].push(pq2[i][j].top());
}