WEIRD 문제에서 계속 시간초과가 나는데 부분집합의 합을 구하는 알고리즘을 잘 모르겠습니다.

  • jungmin1237
    jungmin1237

    안녕하세요.
    C언어로 WEIRD 문제를 풀려고 Backtracking, DP 등등을 참고해가면서
    부분집합의 해를 구하는 알고리즘을 찾아서 풀었는데 계속 시간초과가
    나네요... 제가 생각했을 때에는 제가 구현한 아래의 진약수로 구성된
    집합의 부분집합의 해를 구하는 과정에서 시간이 오래걸리는 거 같습니다.
    재귀호출로 구현하면 안되는건가요?

    혹시 몰라 전체 소스코드를 두번째 문단에 추가합니다.

    // set은 진약수들이 들어있는 배열로, qsort를 가져다가 정렬했습니다.
bool chkSumSameNum(int* set, int len, int sum, int target)
{
    if(sum == target)
        return true;
    if(sum < target || target < 0)
        return false;
    if(chkSumSameNum(set, len-1, sum-set[len-1], target-set[len-1]))
        return true;
    return chkSumSameNum(set,len-1, sum-set[len-1], target);
}


    #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define divfor(i, n) for(i=1; i*i<=n; ++i)

int numcmp(const void*, const void*);
bool chkSumSameNum(int*, int, int, int);

int main()
{
    int cases, num, sumOvernum, idx, divslen;
    register int i;

    scanf("%d", &cases);
    while(cases--){
        int divs[BUFSIZ] = {0,};
        sumOvernum = idx = 0;
        scanf("%d", &num);
        divfor(i, num){
            if(!(num%i)){
                sumOvernum += i;
                divs[idx++] = i;
                if((num/i != i) && (num/i!=num)){
                    sumOvernum += (num/i);
                    divs[idx++] = (num/i);
                }
            }
        }
        divslen = idx-1;
        if(sumOvernum <= num)
            printf("not weird\n");
        else{
            qsort(divs, idx, sizeof(int), numcmp);
            if(chkSumSameNum(divs, divslen, sumOvernum, num))
                printf("not weird\n");
            else
                printf("weird\n");
        }

    }

    return EXIT_SUCCESS;
}

bool chkSumSameNum(int* set, int len, int sum, int target)
{
    if(sum == target)
        return true;
    if(sum < target || target < 0)
        return false;
    if(chkSumSameNum(set, len-1, sum-set[len-1], target-set[len-1]))
        return true;
    return chkSumSameNum(set,len-1, sum-set[len-1], target);
}

int numcmp(const void* a, const void* b)
{
    int na = *(int*)a, nb = *(int*)b;
    if(na > nb)
        return 1;
    else if(na == nb)
        return 0;
    else
        return -1;
}

    4년 전
0개의 댓글이 있습니다.

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