gaelim   2년 전

7% 쯤에 시간초과가 뜹니다

어떤 알고리즘을 사용해서 풀어야할지 모르겠어요 ...



#include <stdio.h>

int main(){

  int i, j, time, num, max, tmp, flag;
  int arr[100000];

  //init
  scanf("%d", &num);
  for (i=0;i<num; i++){
    scanf("%d",&arr[i]);
    arr[i] = 1<<arr[i];
    scanf("%d",&tmp);
    tmp=1<<(tmp+1);
    arr[i]=tmp-arr[i];
  }

  for(i=0, max=0;i<num;i++){
    j=0;
    time=arr[i];
    tmp=1;
    while(1){
      flag=0;
      if (!(time&arr[j]))
      {
        time|=arr[j];
        tmp++;
        flag=1;
      }
      if(j==num-1) {j=0; if (!flag) break;}
      j++;
    }
    if (max<tmp) max=tmp;
  }

  printf("%d\n", max);

}

sgchoi5   2년 전

그리디 알고리즘 입니다. 힌트에도 나와 있는데..

문제에 대한 상세한 설명과 코드를 알고리즘 문제해결 전략 그리디 편에서 보실 수 있습니다.

gaelim   2년 전

감사합니다

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