문제 102번 이렇게 풀었는데 느리네요...

  • 공상가
    공상가

    #include
    #define MAX 500000
    void bitplus(bool*, int);
    void program();
    int main() {
    int i, casen;
    scanf("%d",&casen);
    for(i=0;i program();
    }
    void program() {
    int arr[MAX]={0};
    bool bit_vector[MAX]={false},weird;
    int sum2,sum=0,arrindex=0;
    int i, num;
    scanf("%d",&num);
    if(num==0) {
    printf("not weirdn");
    return;
    }
    for(i=1;i*i<=num;i++) {
    if(!(num%i)) {
    arr[arrindex++]=i;
    if(num/i!=i&&num/i!=num) {
    arr[arrindex++]=num/i;
    }
    }
    }
    for(i=0;i sum+=arr[i];
    }
    if(sum>num) weird=true;
    else weird=false;
    do {
    bitplus(bit_vector,arrindex);
    sum=sum2=0;
    for(i=0;i<arrindex;i++) {
    if(bit_vector[i]) {
    sum+=arr[i];
    } else {
    sum2+=arr[i];
    }
    }
    if(sum==num||sum2==num) {
    weird=false;
    break;
    }
    } while(sum2!=arr[arrindex-1]);
    if(weird) printf("weirdn");
    else printf("not weirdn");
    }
    void bitplus(bool* bit, int len) {
    if(!bit[0]) {
    bit[0]=true;
    return;
    } else {
    int i=0;
    do {
    bit[i++]=false;
    } while(bit[i]&&i<len);
    bit[i]=1;
    }
    }
    머리를 짤 수 있는대로 다 짜봤는데...
    검사 프로그램에서 1000ms이상을 주네요...
    2^n승이 나왔다면... 요건 2^n-1인데.. 사실 그 차이가.. 어마어마하긴 어마어마했어요...(a Subset 과 ~a Subset을 한번에..)
    대신 저기... Bit_vector로 계산해야 한다는 점이.. 좀 기분이 나쁘네요...ㅠ_ㅠ;;
    괜히 저것만 좀 줄이기만 혀도... 속도가 꽤나 증가할텐데;;;
    이 알고리즘으로.. 더 줄일 방법 없을까요?.....

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    ^^; 2^n 과 2^(n-1) 은 두 배의 차이가 있긴 합니다만.. 어차피 2^25 이상의 계산량이 되면 시간 제한 안에 계산하는 것은 무리일 겁니다. n=70 이기 때문에, 이 방법으로는 어떻게 최적화해도 시가 ㄴ안에 풀 수 없을 거 같네여 ㅜㅜ


    15년 전 link
  • 공상가
    공상가

    아흙 ㅠ_ㅠ 그렇군요 ㅠ_ㅠ.... 나름대로.. "오!! 또 효율화 시켰어!!!"라는 환호성과 함께 기쁨에 쩔었는데 ...ㅠ_ㅠ;;;
    이 방법은 어떻게 해도... O(2^n)을 벗어나기 힘들겠군요....


    15년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.