글 읽기 - 낚시왕 '시간초과' .. 반례 찾는 것을 도와주실 수 있으신 분 계신가요

beenpow 4년 전 0

안녕하세요.

'낚시왕' 문제를 붙들고 있는 1인입니다.

일단, 질문 게시판에 있는 올려주신 반례들과 문제에 있는 테스트 케이스 및 제가 만든 테스트 케이스들로 실험을 해 보았습니다.

모두 정확한 정답이 나오며, 어떤 반례에서 '시간초과'가 나는지 찾아내지 못했습니다.

아직 제가 코딩이 익숙하지 않아서 코드가 읽기 어렵지만, 시간내어 읽어주시고 문제점이 혹시나 보인다면 답글 부탁드립니다!

미리 감사합니다!

#include<stdio.h>
#define MAX_R 103
#define inf 987654321
#define MAX_M MAX_R*MAX_R
#define DEBUG 0
int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int R,C;
int M;
int board[MAX_R][MAX_R];

struct SHARK{
    int alive;
    int x;
    int y;
    int spd;
    int dir;
    int sz;
};
int sh_cnt;
SHARK sh[MAX_M];

int gotcha;
void DFS(int rest, int idx);

int main(){
    /* Get input */
    scanf("%d %d %d",&R,&C,&M);
    for(int i=0;i<M;i++){
        scanf("%d %d %d %d %d",&sh[sh_cnt].x,&sh[sh_cnt].y,&sh[sh_cnt].spd,&sh[sh_cnt].dir,&sh[sh_cnt].sz);
        sh[sh_cnt].alive = 1;
        sh_cnt++;
    }
    
    int time = 0;
    while(time < C+1){
        /* 1. man move to column : 'time' */
        {
            time++;
        }
        
        /* 2. Catch the shark */
        {
            int sh_No=0,sh_row=inf;
            // 2-1 Find the closest shark
            for(int i=0;i<sh_cnt;i++){
                if(sh[i].alive == 1 && sh[i].y == time && sh[i].x < sh_row){
                    sh_No = i;
                    sh_row = sh[i].x;
                }
            }
            // 2-2 kill it
            if(sh_row!=inf){
                sh[sh_No].alive = 0;
                gotcha += sh[sh_No].sz;
            }
        }
        
        /* 3. Update sharks */
        {
            // 3-1 Update shark's position
            for(int i=0;i<sh_cnt;i++){
                if(!sh[i].alive) continue;
                int rest=0;
                // 3-1-1 moving colum line
                if(sh[i].dir <3){
                    rest = sh[i].spd % (R*2-2);
                    if(sh[i].x==1){if(sh[i].dir==1) sh[i].dir=2;}
                    if(sh[i].x==R){if(sh[i].dir==2) sh[i].dir=1;}
                }
                // 3-1-2 moving row line
                else{
                    rest = sh[i].spd % (C*2-2);
                    if(sh[i].y==1){if(sh[i].dir==4) sh[i].dir=3;}
                    if(sh[i].y==C){if(sh[i].dir==3) sh[i].dir=4;}
                }
                DFS(rest, i); // 각 방향별로 rest=0일때까지 계속 핑퐁 시켜서 위치 찾게 하기.
                
            }
            // 3-2 If there are sharks in same position, someone have to die.
            for(int i=0;i<sh_cnt;i++){
                for(int k=i+1;k<sh_cnt;k++){
                    if(!sh[i].alive || !sh[k].alive) continue;
                    if(sh[i].x == sh[k].x && sh[i].y == sh[k].y){
                        if(sh[i].sz < sh[k].sz) sh[i].alive = 0;
                        else                    sh[k].alive = 0;
                    }
                }
            }
        }
    }
    /* 4. Print out */
    printf("%d\n",gotcha);
    
    
    
    return 0;
}
void DFS(int rest, int idx){
    if(sh[idx].dir==1){
        if(rest >= sh[idx].x){
            sh[idx].dir = 2;
            rest = rest- sh[idx].x+1;
            sh[idx].x = 1;
            DFS(rest,idx);
        }
        else{
            sh[idx].x = sh[idx].x - rest;
        }
    }
    else if(sh[idx].dir==2){
        if(rest > R - sh[idx].x){
            sh[idx].dir = 1;
            rest -= ( R - sh[idx].x );
            sh[idx].x = R;
            DFS(rest,idx);
        }
        else{
            sh[idx].x = sh[idx].x + rest;
        }
    }
    else if(sh[idx].dir==3){
        if(rest > C - sh[idx].y){
            sh[idx].dir = 4;
            rest -= ( C - sh[idx].y );
            sh[idx].y = C;
            DFS(rest,idx);
        }
        else{
            sh[idx].y = sh[idx].y + rest;
        }
    }
    else{
        if(rest >= sh[idx].y){
            sh[idx].dir = 3;
            rest = rest - sh[idx].y+1;
            sh[idx].y = 1;
            DFS(rest,idx);
        }
        else{
            sh[idx].y = sh[idx].y - rest;
        }
    }
}

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

문제

문제

출처

ICPC

낚시왕 '시간초과' .. 반례 찾는 것을 도와주실 수 있으신 분 계신가요

beenpow 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말