Solution (1)

• 우선 각 상어의 정보를 담고 있는 구조체를 선언해 주었다. 낚시꾼에 대한 구현은 어렵지 않게 해결 할 수 있었으며, 상어의 이동을 관리하는 것이 이 문제의 관건이였다. 그래서 2차원 벡터의 자료형을 해당 구조체로 선언하여주어 상어 관리를 편하게 해주었다.
• 처음에는 상어의 속력을 사용하여 for문을 순회하며 일일히 좌표를 더해주었는데, 시간초과가 발생하였다.
• worst case에서 100 x 100 x 1000의 시간복잡도가 발생하기에 시간초과는 당연한 결과이며 이를 해결하기 위한 방법을 고민하였다.

Solution (2)

• 생각해보니, R, C의 moduler 연산과 divide 연산으로 쉽게 상어의 위치를 예측 할 수 있었고, 이를 사용하여 시간복잡도를 줄여주었다.

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct shark
{
    int r;
    int c;
    int s;
    int d;
    int z;
};

int R, C, M;
vector<vector<shark>> arr(201, vector<shark>(201));
vector<vector<shark>> t_arr(201, vector<shark>(201));
int fisher = 0;
int answer;

void fishing()
{
    for (int i = 1; i <= R; i++)
    {
        if (arr[i][fisher].c != 0)
        {
            answer += arr[i][fisher].z;
            shark temp = {0, 0, 0, 0, 0};
            arr[i][fisher] = temp;
            break;
        }
    }
}

void move_shark(int y, int x)
{
    int r = arr[y][x].r;
    int c = arr[y][x].c;
    int s = arr[y][x].s;
    int d = arr[y][x].d;
    int z = arr[y][x].z;

   
    if(d == 1){
        int temp = s- (r-1);
        if(temp <= 0){
            r += dy[d] * s;
            c += dx[d] * s;
        }
        else{
            r = 1;
            int temp2 = temp % (R-1);
            int temp3= temp / (R-1);
            if(temp3 % 2 == 0){
                d = 2;
            }
            else{
                r = R;
            }
            r += dy[d] * temp2;
            c += dx[d] * temp2;
          
        }
    }
    else if(d == 2){
        int temp = s-(R-r);
        if(temp <= 0){
            r += dy[d] * s;
            c += dx[d] * s;
        }
        else{
            r = R;
            int temp2 = temp % (R-1);
            int temp3 = temp / (R-1);
            if(temp3 % 2 == 0){
                d = 1;
            }
            else{
                r = 1;
            }
            r += dy[d] * temp2;
            c += dx[d] * temp2;
          
        }
    }
    else if(d == 3){
        int temp = s-(C-c);
        if(temp <= 0){
            r += dy[d] * s;
            c += dx[d] * s;
        }
        else{
            c = C;
            int temp2 = temp % (C-1);
            int temp3 = temp / (C-1);
            if(temp3 % 2 == 0){
                d = 4;
            }
            else{
                c = 1;
            }
            r += dy[d] * temp2;
            c += dx[d] * temp2;
           
        }
    }
    else if(d == 4){
        int temp = s- (c-1);
        if(temp <= 0){
            r += dy[d] * s;
            c += dx[d] * s;
        }
        else{
            c = 1;
            int temp2 = temp % (C-1);
            int temp3= temp / (C-1);
            if(temp3 % 2 == 0){
                d = 3;
            }
            else {
                c = C;
            }
            r += dy[d] * temp2;
            c += dx[d] * temp2;
        }
    }

  

    if (t_arr[r][c].c != 0)
    {
        if (t_arr[r][c].z > z)
        {
        }
        else
        {
            t_arr[r][c] = {r, c, s, d, z};
        }
    }
    else
    {
        t_arr[r][c] = {r, c, s, d, z};
    }
}

void Solution()
{
    while (fisher <= C)
    {
        fisher++;
        for (int i = 1; i <= R; i++)
        {
            for (int j = 1; j <= C; j++)
            {
                t_arr[i][j] = {0, 0, 0, 0, 0};

            }

        }

        fishing();
        for (int i = 1; i <= R; i++)
        {
            for (int j = 1; j <= C; j++)
            {
                if (arr[i][j].c != 0)
                {
                    move_shark(i, j);
                }
            }
        }
        for (int i = 1; i <= R; i++)
        {
            for (int j = 1; j <= C; j++)
            {
                arr[i][j] = t_arr[i][j];
            }
        }
    }
    cout << answer << '\n';
}

void Input()
{
    cin >> R >> C >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        shark temp = {a, b, c, d, e};
        arr[a][b] = temp;
    }
}

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

    Input();
    Solution();
}