글 읽기 - [C] 낚시왕 시간초과 도저히 모르겠습니다..

eunddubi 4년 전 0

다른 질문글에 나와있는 예제들도 답은 다 나오는데 시간초과가 뜨니 답답하네요.

코딩을 많이 해보지 않아 미숙하지만 첨삭부탁드립니다.

#include <stdio.h>
#include <stdlib.h>
#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4
#define EMPTY 99999

int R,C,M;
int **pool;
int answer=0;
typedef struct shark{
  int r;
  int c;
  int s; //speed
  int d; //direction
  int z; //size
}shark;
shark *slist;

void swimming(){
  int i,j;
  int len;
  int loser, winner;
  for(i=0;i<M;i++){
    if(slist[i].r == 1 && slist[i].d == UP){
      slist[i].d = DOWN;
    }else if(slist[i].r == R && slist[i].d == DOWN){
      slist[i].d = UP;
    }else if(slist[i].c == 1 && slist[i].d == LEFT){
      slist[i].d = RIGHT;
    }else if(slist[i].c == C && slist[i].d == RIGHT){
      slist[i].d = LEFT;
    }
  }
  for(i=0;i<M;i++){
    if(slist[i].r != 0 && slist[i].c != 0){
      len = slist[i].s;
      pool[slist[i].r][slist[i].c] = EMPTY;
      while(len){
        if(slist[i].d == UP){
          slist[i].r--;
          if(slist[i].r == 1){
            slist[i].d = DOWN;
          }
        }else if(slist[i].d == DOWN){
          slist[i].r++;
          if(slist[i].r == R){
            slist[i].d = UP;
          }
        }else if(slist[i].d == LEFT){
          slist[i].c--;
          if(slist[i].c == 1){
            slist[i].d = RIGHT;
          }
        }else if(slist[i].d == RIGHT){
          slist[i].c++;
          if(slist[i].c == C){
            slist[i].d = LEFT;
          }
        }
        len--;
        }
    }
  }
  for(i=0;i<M-1;i++){
    for(j=i+1;j<M;j++){
      if(slist[i].r && slist[j].r &&slist[i].r == slist[j].r && slist[i].c == slist[j].c){
        if(slist[i].z > slist[j].z){
          loser = j;
        }else{
          loser = i;
        }
        slist[loser].r = 0;
        slist[loser].c = 0;
      }
    }
  }
  for(i=0;i<M;i++){
    if(slist[i].r != 0 && slist[i].c != 0){
        pool[slist[i].r][slist[i].c] = i;
    }
  }
}

int main(){
  int i,j;
  int gotta = 0;
  int adjustR, adjustC;

  scanf("%d %d %d",&R, &C, &M);

  pool = (int**)malloc(sizeof(int*)*(R+1));
  for(i=0;i<=R;i++){
    pool[i] = (int*)calloc((C+1), sizeof(int));
  }
  for(i=0;i<=R;i++){
    for(j=0;j<=C;j++){
      pool[i][j] = EMPTY;
    }
  }

  slist = (shark*)calloc(M,sizeof(shark));
  for(i=0;i<M;i++){
    scanf("%d %d %d %d %d", &slist[i].r, &slist[i].c, &slist[i].s, &slist[i].d, &slist[i].z);
    pool[slist[i].r][slist[i].c] = i;
  }

  adjustR = R + (R-2);
  adjustC = C + (C-2);

  for(i=0;i<M;i++){
    if(slist[i].s >= adjustR && (slist[i].d == UP || slist[i].d == DOWN)){
      slist[i].s %= adjustR;
    }else if(slist[i].s >= adjustC && (slist[i].d == LEFT || slist[i].d == RIGHT)){
      slist[i].s %= adjustC;
    }
  }

  for(i=1;i<=C;i++){
    j = 1;
    while(j<=R){
      if(pool[j][i] != EMPTY){
        gotta = pool[j][i];
        answer += slist[gotta].z;
        slist[gotta].r = 0;
        slist[gotta].c = 0;
        pool[j][i] = EMPTY;
        break;
      }
      j++;
    }
    swimming();
  }
  printf("%d\n",answer);

  for(i=0;i<=R;i++){
    free(pool[i]);
  }
  free(pool);
  free(slist);
  return 0;
}

james_kylee 4년 전 1

66~78라인에서 시간초과가 나옵니다. M이 최대 1만개인데 매번 1만개 중에서 2개를 모두 조사하는 방식으로는 지나치게 오랜 시간이 걸립니다.

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

문제

문제

출처

ICPC

[C] 낚시왕 시간초과 도저히 모르겠습니다..

eunddubi 4년 전 0

james_kylee 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말