[C++] 백준 17143번: 낚시왕 - Implementation

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

17143번: 낚시왕

 

그야말로 빡구현.. 3시간 풀로 집중하고 노트 열심히 써가면서 구현했다

 

처음에는 별 것 없다고 생각했는데, 의외로 벽을 튕기고 나온 상어를 구현하기가 까다로웠다.

 

나머지 연산을 이용해서 상어의 위치를 업데이트 해주려 했으나,

상어가 양수 방향으로 이동할 때는 별 문제가 없었지만

상어가 음수 방향으로 이동할 때 과부하가 걸려서 엄청 헤맸던 문제

 

그리고 구현하고 보니까 같은 공간에 위치한 상어는

사이즈가 큰 상어만 남는다는 조건을 또 잘못 구현해서

처음 제출하고 틀렸을 때 멘탈이 많이 나갔었던 문제..

 

상어의 좌표를 (x, y)라고 한다면,

(d == 0 || d == 1) 인 경우 상어는 위아래로만 움직이고

(d == 2 || d == 3) 인 경우 상어는 좌우로만 움직이므로

d에 따라 조건을 달리해주었다.

 

만약 d가 2 (오른쪽으로 이동) 이고, 상어의 좌표가 (x, 1)이라면 

가로 길이 m까지 갔다가 다시 1로 돌아오는 움직임을 반복할 것이다.

즉, 1 부터 m 까지 총 (m - 1)번 움직이고, m 부터 1 까지 다시 (m - 1)번을 움직인다.

 

그렇기에 왕복하는 횟수는 스피드 s / (m - 1)번이 될것이고,  남은 거리는 나머지인 s % (m - 1)이 될 것이다.

그리고 좌표가 1부터가 아닌 y부터시작이라면 간단하게 (y - 1)을 더 가주면 된다.

 

이렇게 생각해서 d == 2, d == 1일때는 간단하게 구현했으나, 음수일때의 구현을 멍청하게 생각했다..

결국 1부터가 아닌 m부터 시작으로 바꾸고, y부터 시작이라면 (m - y) 번 더 움직이면 된다는 것을

생각을 잘못해서 너무 오래걸렸다..

 

내 풀이가 정해인지는 모르겠으나

TLE가 안 뜬 것을 보면 나머지 연산을 이용해서 푸는 방법이 맞는 것 같기도..?

 

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
vector<tuple<int,int,int>>v[101][101], vec[101][101];
bool flag;
int main(){
    int n, m, t, r, c, s, d, z, x, y, nx, ans=0; cin >> n >> m >> t;
    while(t--){
        cin >> r >> c >> s >> d >> z;
        d--;
        v[r][c].push_back({s,d,z});
    }
    for(int i=1; i<=m; i++){
        flag=false;
        for(int j=1; j<=n; j++){
            if(!v[j][i].empty()) {
                ans+=get<2>(v[j][i][0]);
                flag=true;
                v[j][i].clear();
            }
            if(flag) break;
        }
        for(int p=1; p<=n; p++){
            for(int q=1; q<=m; q++){
                if(!v[p][q].empty()){
                    auto cur=v[p][q][0];
                    v[p][q].pop_back();
                    s=get<0>(cur), d=get<1>(cur), z=get<2>(cur);
                    if(d==0){
                        flag=false;
                        x=s/(n-1), y=s%(n-1);
                        if(x%2==0) y=n-y;
                        else flag=true, d=1, y++;
                        nx=n-p;
                        while(nx--){
                            flag ? y++ : y--;
                            if(y>n) y=n-1, d=0, flag=false;
                            else if(y<1) y=2, d=1, flag=true;
                        }
                        if(!vec[y][q].empty()){
                            if(get<2>(vec[y][q][0])<z){
                                vec[y][q].pop_back();
                                vec[y][q].push_back({s,d,z});
                            }
                        }
                        else vec[y][q].push_back({s,d,z});
                    }
                    else if(d==1){
                        flag=true;
                        x=s/(n-1), y=s%(n-1);
                        if(x%2==0) y++;
                        else flag=false, d=0, y=n-y;
                        nx=p-1;
                        while(nx--){
                            flag ? y++ : y--;
                            if(y>n) y=n-1, d=0, flag=false;
                            else if(y<1) y=2, d=1, flag=true;
                        }
                        if(!vec[y][q].empty()){
                            if(get<2>(vec[y][q][0])<z){
                                vec[y][q].pop_back();
                                vec[y][q].push_back({s,d,z});
                            }
                        }
                        else vec[y][q].push_back({s,d,z});
                    }
                    else if(d==2){
                        flag=true;
                        x=s/(m-1), y=s%(m-1);
                        if(x%2==0) y++;
                        else flag=false, d=3, y=m-y;
                        nx=q-1;
                        while(nx--){
                            flag ? y++ : y--;
                            if(y>m) y=m-1, d=3, flag=false;
                            else if(y<1) y=2, d=2, flag=true;
                        }
                        if(!vec[p][y].empty()){
                            if(get<2>(vec[p][y][0])<z){
                                vec[p][y].pop_back();
                                vec[p][y].push_back({s,d,z});
                            }
                        }
                        else vec[p][y].push_back({s,d,z});
                    }
                    else{
                        flag=false;
                        x=s/(m-1), y=s%(m-1);
                        if(x%2==0) y=m-y;
                        else flag=true, d=2, y++;
                        nx=m-q;
                        while(nx--){
                            flag ? y++ : y--;
                            if(y>m) y=m-1, d=3, flag=false;
                            else if(y<1) y=2, d=2, flag=true;
                        }
                        if(!vec[p][y].empty()){
                            if(get<2>(vec[p][y][0])<z){
                                vec[p][y].pop_back();
                                vec[p][y].push_back({s,d,z});
                            }
                        }
                        else vec[p][y].push_back({s,d,z});
                    }
                }
            }
        }
        for(int p=1; p<=n; p++){
            for(int q=1; q<=m; q++){
                v[p][q]=vec[p][q];
                vec[p][q].clear();
            }
        }
    }
    cout << ans;
}