WEIRD 오답

  • ghlee0228
    ghlee0228

    왜 오답이 나오는지 모르겠습니다.
    20000까지 weird num만 출력되도록 테스트 해봤을때도
    문제없이 잘 나오는거 같은데...
    도와주세요!

    코드

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX 250000
    
    int divisors[MAX] = { 0 };
    int *sub_divisors;
    int sub_max_idx = 0;
    int diff = 0 ;
    int sub_sum = 0;
    
    enum RESULT { FALSE, TRUE };
    
    int getDivisors(int num);
    int verify(int num);
    int equalNum(int* subArrayt);
    
    int getDivisors(int num)
    {
        int i, j;
    
        for (i = 1, j = 0; i <= num / 2; i++)
        {
            if (num%i == 0)
            {
                divisors[j] = i;
                j++;
            }
        }
    
        return j;
    }
    
    int verify(int num)
    {   
        int sum = 0;
        int i = 0, max_idx = 0; 
        int ret;
    
        max_idx = getDivisors(num);
        // Condition 1. num 초과
        for (i = 0; i < max_idx; i++)
        {
            sum += divisors[i];
        }
        if (sum <= num) return FALSE;
    
        // Condition 2. no subset such that sum of subset = num 
        diff = sum - num;
        for (sub_max_idx = 0; sub_max_idx < max_idx; sub_max_idx++)
            if (divisors[sub_max_idx] > diff) break;
    
        sub_divisors = (int *)malloc(sizeof(int)*sub_max_idx);
        for (i = 0; i < sub_max_idx; i++)
            sub_divisors[i] = divisors[sub_max_idx - i - 1];
    
        ret = equalNum(sub_divisors);
        free(sub_divisors);
        sub_sum = 0;
    
        return ret;
    }
    
    int equalNum(int* subArray)
    {
        int pivot = 0;
        int i = 0;
    
        for (pivot = 0; pivot < sub_max_idx; pivot++)
        {
            sub_sum += subArray[pivot];
            if (sub_sum == diff) return FALSE;
            for (i = pivot + 1; i < sub_max_idx; i++)
            {
                sub_sum += subArray[i];         
                if (sub_sum == diff) return FALSE;
                else if (sub_sum > diff)
                {
                    sub_sum -= subArray[i];
                }                       
            }       
            sub_sum -= subArray[pivot];
        }
    
        return TRUE;
    }
    
    
    int main()
    {
        int num;
        int condition;
        int testcase;
    
        scanf("%d", &testcase);
        while (testcase--)
        {
            memset(divisors, 0, sizeof(int)*MAX);
            scanf("%d", &num);
            condition = verify(num);
    
            if (condition == TRUE) printf("weird\n");
            else if (condition == FALSE) printf("not weird\n");
        }
    
        return 0;
    }
    

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