17143. 낚시왕

시뮬레이션 문제.

 

처음엔 쉬울 줄 알았지만, 

하나하나 구현하며 오류가 많아 실제로 푸는데는 꽤 오래걸렸다.

해결방법은 문제에 주어진 대로 코드를 쭉 구성해가면 된다.

 

우선, 시간복잡도를 계산했을 때,

0 낚시왕이 모든 열을 걸어가는 시간 O(N)

    1 낚시하는 시간(모든 행을 살핌) O(N),

    2 맵을 다시 만드는 시간 O(N^2),

    3 모든 상어에 대해 O(N^2)

        3-1 상어가 이동하는데 걸리는 시간 O(N)

 

따라서 최악은 O(N^4)이 걸린다. 100x100x100x100 = 1억이므로 시간 내에 해결이 가능하다고 생각했다.

 

상어가 있는 물을 w[101][101]로 만들고,

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

    C(column)을 바꾸어가며,

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.

    R(row)를 살펴 상어가 있으면 잡았다.

3. 상어가 이동한다.

   이거에 대해서 아이디어를 내는데 시간이 좀 걸렸다.

   속도에 따라 모든 시간을 일일이 탐색하면 시간이 많이 걸릴 것 같아서,

   원래 자리로 돌아오는데 주기가 얼마인지 구했다. 일일이 해보면서 규칙을 찾았고, 2(n-1)주기를 가짐을 알았다.

    speed % (2 * (n - 1)) 연산을 하였으므로, O(S) --> O(N) 시간으로 단축되었다. (S<= 1000, N <=100)

 

마지막으로, 겹친 상어 중 크기가 가장 큰 상어가 살아남아야 했는데,

처음부터 로직을 잘 짜고 코드를 만들어야 했었다. 이것 때문에.. 시간을 좀.. 날렸지만

교훈을 얻었다. 로직을 먼저 잘 짜자.

 

#include <cstdio>
#include <vector>
using namespace std;
int dx[] = {0, -1, 1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};

struct shark{
    int r, c, s, d, z;
    bool live = false;
};
vector<shark> sharks(10001);
int w[101][101];
int R, C, M;

void init_water(){
    for (int i=1; i<=R; ++i){
        for (int j=1; j<=C; ++j){
            w[i][j] = 0;
        }
    }
}

int main() {
    scanf("%d %d %d", &R, &C, &M);
    int r, c, s, d, z;
    shark tmp;
    for (int i=1; i<=M; ++i){
        scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
        tmp.r = r, tmp.c = c, tmp.s = s, tmp.d = d, tmp.z = z, tmp.live = true;
        sharks[i] = tmp;
        w[r][c] = i;
    }

    int ans = 0;
    for (int step=1; step<=C; ++step){
        // fishing O(N)
        for (int row=1; row<=R; ++row){
            int shark_num = w[row][step];
            if (shark_num > 0 && sharks[shark_num].live){
                ans += sharks[shark_num].z;
                sharks[shark_num].live = false;
                w[row][step] = 0;
                break;
            }
        }
        if (step == C) break;


        init_water();

        // move
        int shark_idx = 0;
        for (auto it = sharks.begin() + 1; it != sharks.end(); ++it){
            ++shark_idx;
            if (!sharks[shark_idx].live) continue;
            int& x = it->r;
            int& y = it->c;
            int speed = it->s;
            int& d = it->d;

            int nx = x;
            int ny = y;
            if (d == 1 || d == 2){ // up, down
                int cnt = speed % (2 * (R-1));
                while(cnt > 0){
                    if (0 >= nx + dx[d] || nx + dx[d] > R){
                        if (d == 1) d = 2;
                        else d = 1;
                    }
                    nx += dx[d];
                    --cnt;
                }
            }
            else if (d == 3 || d == 4){ // left, right
                int cnt = speed % (2 * (C-1));
                while(cnt > 0){
                    if (0 >= ny + dy[d] || ny + dy[d] > C){
                        if (d == 3) d = 4;
                        else d = 3;
                    }
                    ny += dy[d];
                    --cnt;
                }
            }
            x = nx;
            y = ny;

            if (w[x][y] > 0){
                if (sharks[w[x][y]].z < (it->z)) {
                    // kill
                    sharks[w[x][y]].live = false;
                    w[x][y] = shark_idx;
                }
                else {
                    it->live = false;
                }
            }
            else w[x][y] = shark_idx;
        }
    }
    printf("%d\n", ans);
    return 0;
}