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

1. 문제설명

낚시왕이 되는 일은 꽤 어려운 일인지도 모릅니다.

어부는 오른쪽 열로 한칸 씩 이동하면서 

어부가 서있는 열에서 가장 가까운 상어를 잡습니다.

상어는 어부가 한칸 움직일 때마다 각각의 방향과 속도로 움직입니다.

만약 모든 상어가 움직인 후 같은 칸에 상어가 두마리 있을 경우 크기가 큰 상어만 남습니다.

어부가 끝까지 이동한 후 잡은 상어의 크기 합을 출력하면 됩니다.

2.접근방법[알고리즘]

이 문제를 해결하기 위해 특별히 필요한 알고리즘은 없습니다.

문제에서 제시한 조건 대로 구현하면 됩니다.

1. 어부가 오른쪽 열로 한칸 움직이고 가장 가까운 상어를 잡는다.

2. 상어 모두 각각 움직인다.

3. 겹치는 상어가 있으면 크기가 큰 것만 남긴다.

상어의 움직임을 구현하는 게 이 문제의 핵심입니다.

Input

상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.

전체 격자판 최대 크기는 100*100인데

상어의 속도는 1000이 최댓값이기 때문에

1000을 그대로 사용한다면 불필요한 움직임이 많이 포함됩니다.

상어가 열이나 행을 왕복하는데 필요한 거리는 r, c 값에 따라 고정되어 있기 때문에

연산을 통해 속도를 빼줄 수 있습니다.

if (d <= 2) s %= (r - 1) * 2;
else s %= (c - 1) * 2;

(r-1)*2 번이나 (c-1)*2 번 왔다갔다 하면 상어가 제자리에 놓이기 때문에

불필요한 연산을 줄여줄 수 있습니다.

이 과정을 거치지 않으면 시간초과가 납니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int r, c, m, ans;

struct Shark {
	bool isin = 0;
	int s = 0, d = 0, z = 0;
};

Shark ch[103][103];

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };

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

	cin >> r >> c >> m;
	for (int i = 0; i < m; i++) {
		int a, b, s, d, z;
		cin >> a >> b >> s >> d >> z;

		//상어의 반복움직임 제거
		if (d <= 2) s %= (r - 1) * 2;
		else s %= (c - 1) * 2;

		ch[a][b] = { 1,s,d,z };
	}


	for (int i = 1; i <= c; i++) {

		Shark moved[103][103];

		//해당 열에서 상어 잡기 
		for (int j = 1; j <= r; j++) {
			if (ch[j][i].isin) {
				ans += ch[j][i].z;
				ch[j][i] = { 0,0,0,0 };
				break;
			}
		}

		// 상어 이동 
		for (int j = 1; j <= r; j++) {
			for (int k = 1; k <= c; k++) {
				if (ch[j][k].isin) {
					int nx = j;
					int ny = k;

					for (int q = 0; q < ch[j][k].s; q++) {
						if (ch[j][k].d == 1) {
							//벽 만난 경우 방향전환
							if (nx == 1) {
								ch[j][k].d = 2;
								q--;
								continue;
							}
							nx += dx[0];
							ny += dy[0];

						}
						else if (ch[j][k].d == 2) {
							if (nx == r) {
								ch[j][k].d = 1;
								q--;
								continue;
							}

							nx += dx[1];
							ny += dy[1];

						}
						else if (ch[j][k].d == 3) {
							if (ny == c) {
								ch[j][k].d = 4;
								q--;
								continue;
							}
							nx += dx[2];
							ny += dy[2];

						}
						else if (ch[j][k].d == 4) {
							if (ny == 1) {
								ch[j][k].d = 3;
								q--;
								continue;
							}
							nx += dx[3];
							ny += dy[3];
						}

					}
					// 같은 칸에 상어 두마리가 있는 경우
					// 크키가 큰 상어만 남긴다.
					if (moved[nx][ny].isin) {
						if (moved[nx][ny].z < ch[j][k].z) {
							moved[nx][ny] = { 1,ch[j][k].s,ch[j][k].d,ch[j][k].z };
						}
					}
					else {
						moved[nx][ny] = { 1,ch[j][k].s,ch[j][k].d,ch[j][k].z };
					}

				}
			}
		}
		// moved 배열에 있는 값을 ch배열로 복사해주고 
		// ch배열을 통해 어부가 이동한후 다시 계산하도록 해준다.
		memcpy(&ch, &moved, sizeof(moved));
	}

	cout << ans << '\n';
	return 0;
}

백준 17143번 낚시왕 테스트케이스 및 반례

50 50 19
4 9 21 1 999
50 50 4 4 500
50 49 222 3 200
50 48 12 2 45
50 47 36 1 900
2 3 20 3 444
4 8 4 2 49
3 3 40 4 50
2 2 460 2 4444
48 23 500 3 12
1 1 200 1 123
44 44 123 3 125
44 40 222 3 17
40 44 333 3 57
18 40 1 1 4
3 10 50 2 406
1 36 177 4 50
1 46 120 4 7
1 50 28 4 54

정답 7718