글 읽기 - [C++] 17143번 반례가 있을까요?

gi5005 3년 전 0

기본 예제와 게시판에 있는 예제들을 돌려봤는데 정상적으로 나옵니다. 어디서 놓친 부분이 있는걸까요?

알고리즘은 다음과 같이 했습니다.

1. 상어 위치 입력 , mp , vector shark에 저장

2. (row-1)*2 . (column-1) *2 주기가 있으므로 속력에서 나머지 연산후 저장

3. fishman에 x좌표를 이동시켜주면서 Y좌표 가장 작은 상어 탐색후 저장 , 잡은 물고기 무게+

4. 원래 있는 상어 좌표와 겹치면 안되므로 새로운 tmp vector sharkcur 선언

4. 잡힌 물고기 skip, 물고기는 속력만큼 이동하면서 좌표밖으로 나갈시 예외처리

5. 이동한 위치에 자기보다 큰 상어가 있을경우 skip

6. 원래 mp , shark에 tmp, shrakcur 삽입

#include <bits/stdc++.h>
using namespace std;
#define MAX 110
typedef long long ll;
ll dx[5] = {0, 0, 0, 1, -1};
ll dy[5] = {0, -1, 1, 0, 0};
ll R, C, M;
struct Shark
{
    ll y;
    ll x;
    ll speed;
    //d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
    ll dir;
    ll size;
    bool isDead = false;
};
vector<vector<Shark>> mp(MAX, vector<Shark>(MAX, {0, 0, 0, 0, 0, 0}));
bool cmp(Shark s1, Shark s2)
{
    return s1.size > s2.size;
}
void seeM()
{
    cout << "\n";
    for (ll i = 1; i <= R; i++)
    {
        for (ll j = 1; j <= C; j++)
        {
            cout << mp[i][j].size << " ";
        }
        cout << "\n";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // 격자판의 크기 R, C와 상어의 수 M
    ll ans=0;
    cin >> R >> C >> M;
    // (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.
    vector<Shark> shark;
    for (ll i = 0; i < M; i++)
    {
        Shark tmp;
        cin >> tmp.y >> tmp.x >> tmp.speed >> tmp.dir >> tmp.size;
        // 반복되는 주기이다.
        ll rowRp = (R - 1) * 2;
        ll columnRp = (C - 1) * 2;
        // 위아래
        if (tmp.dir <= 2)
            tmp.speed = tmp.speed % rowRp;
        if (tmp.dir > 2)
            tmp.speed = tmp.speed % columnRp;
        mp[tmp.y][tmp.x] = tmp;
        shark.push_back(tmp);
    }
    for (ll fishman = 1; fishman <= C; fishman++)
    {
        seeM();
        if(shark.empty()) break;
        // 가장 가까운 상어 낚는다.
        ll fishCaught = 0;
        for (ll i = 1; i <= R; i++)
        {
            if (mp[i][fishman].size > 0)
            {
                fishCaught = mp[i][fishman].size;
                ans +=mp[i][fishman].size;
                break;
            }
        }
        // 존제 여부
        bool ext[MAX][MAX];
        // 상어가 다 움직인 후 옮겨준다.
        vector<Shark> sharkCur;
        // 상어 위치 저장
        vector<vector<Shark>> tmp(MAX, vector<Shark>(MAX, {0, 0, 0, 0, 0, 0}));
        for (ll i = 0; i < shark.size(); i++)
        {
            Shark cur = shark[i];
            if (cur.size == fishCaught)
                continue;
            // 속력만큼 이동한다.
            for (ll i = 1; i <= cur.speed; i++)
            {
                // 다음 좌표
                cur.x = cur.x + dx[cur.dir];
                cur.y = cur.y + dy[cur.dir];
                // 만약에 좌표 밖으로 넘어 갈 경우 방향 바꿔줌
                if (cur.y <= 0 || cur.y > R || cur.x <= 0 || cur.x > C)
                {
                    if (cur.dir == 1)
                        cur.dir = 2;
                    else if (cur.dir == 2)
                        cur.dir = 1;
                    else if (cur.dir == 3)
                        cur.dir = 4;
                    else if (cur.dir == 4)
                        cur.dir = 3;
                    i-=2;
                }
            }
            // 만약에 상어가 있을경우
            if (ext[cur.y][cur.x])
            {
                // 크기가 작을경우 skip
                if (tmp[cur.y][cur.x].size > cur.size)
                    continue;
            }
            sharkCur.push_back(cur);
            tmp[cur.y][cur.x] = cur;
            ext[cur.y][cur.x] = true;
        }
        shark = sharkCur;
        mp = tmp;
    }
    cout << ans;
}

gi5005 3년 전 0

잡아먹힌 상어를 shark에 넣고있어서 수정했더니 해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 17143번 반례가 있을까요?

gi5005 3년 전 0

gi5005 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말