WEIRD 질문있습니다 ㅠㅠ

  • 빠비
    빠비

    RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow) 와
    RTE (SIGABRT: program aborted, probably assertion fail)
    오류가 계속해서 발생합니다.
    약수가 200개 이상이 될만한 수는 50만 이하로 없다고 생각되어 배열 크기를 200으로 잡았습니다.
    실행시 값은 제대로 나오나 제출하면 계속 런타임 오류가 발생합니다.
    혹시나해서 100개의 값을 넣고 실행시켜봤는데도 에러가 뜨거나 하지 않습니다.
    랜덤 코드 사용하여 200개까지 돌려봤는데 문제 없었습니다ㅠㅠ
    도대체 왜 그런걸까요ㅠㅠ
    제 코드의 문제점이 어디있는 걸까요ㅠㅠ 도와주세요

    /*입력한 수가 괴짜수(weird)인지 판별하여라.
    괴짜수란 자기자신을 제외한 약수의 합(진약수의 합)이 자기보다 크며, 약수의 조합의 합으로 자기자신을 만들 수 없는 수를 말한다.*/
    #include <iostream>
    #include <string>
    using namespace std;
    
    #define MAX_SIZE 200
    
    int setYaksu(int *arr_yak, int number); //약수의 배열와 약수들의 개수를 구하는 함수
    bool isWeird(int *arr_yak, int number, int sum);    //괴짜수인지 체크
    
    int main(){
        int count;  //테스트케이스
        int insert; //weird를 판별하기 위해 입력할 수
        int index;  //약수의 개수
        int *yaksu; //약수들을 넣을 배열
        int sum = 0;
        string *result;
    
        cin>>count;
        if(count<=200){
            result = new string[count];
            yaksu = new int[MAX_SIZE];
            for(int i=0;i<count;i++){
                //cout<<i<<" : ";
                cin>>insert;
                if(insert>0&&insert<500001){
                    index = setYaksu(yaksu, insert);    //약수와 개수를 구함
    
                    //약수의 총합
                    for(int i=0;i<index-1;i++){
                            sum += yaksu[i];
                    }
    
                    //cout<<insert<<"의 진약수 총합은 "<<sum<<endl;
                    //과잉수 판별
                    if(sum>insert){ //자기자신을 제외한 약수의 합(진약수의 합)이 자기보다 크면
                        if(isWeird(yaksu, insert, sum))
                            result[i] = "weird";
                        else
                            result[i] = "not weird";
                    }
                    else{
                        result[i] = "not weird";
                    }
                }
                //사용변수 초기화
                sum = 0;
            }
            /*for(int i=0;i<index;i++){
                cout<<yaksu[i]<<" ";
            }*/
            //cout<<endl;
            for(int i=0;i<count;i++){
                cout<<result[i]<<endl;
            }
            //메모리 해제
            delete []yaksu;
            delete []result;
        }
        return 0;
    }
    
    int setYaksu(int *arr_yak, int number){ //약수의 배열와 약수들의 개수를 구하는 함수
        int index = 0;
        int yak = 0;
        int sum = 0;
        bool isSqrt = false;    //제곱수인지 체크
    
        /*
        약수의 일부분을 먼저 구하면 일부분과 짝이 지어지는 약수가 반드시 있으므로
        number-1까지 전부 나누어보지 않아도 쉽게 약수의 집합을 만들 수 있음
        */
        for(yak=1;(yak*yak)<number;yak++){  //약수의 일부분을 먼저 구함
            if(number%yak==0){
                arr_yak[index] = yak;
                index++;
            }
        }
        if((yak*yak)==number){  //어떤 수의 제곱일 경우
            arr_yak[index] = yak;
            index++;
            isSqrt = true;
        }
        for(int i=index-1;i>=0;i--){    //일부분으로 나머지 약수까지 구함
            if(isSqrt){ //제곱수이면 넘어감
                isSqrt = false;
                continue;
            }
            arr_yak[index] = number/arr_yak[i];
            index++;
        }
        return index;
    }
    bool isWeird(int *arr_yak, int number, int sum){    //괴짜수인지 체크
        int *stack; //재귀를 피하기 위해 만든 배열
        int index = 0;
        int i = 0;
        int top = -1;
        int value = 0;
        int diff =  sum - number;   //약수의 합과 원래 수의 차이를 계산
        int d;
    
        stack = new int[MAX_SIZE];
    
        //cout<<"diff: "<<diff<<endl;
    
        while(arr_yak[index]<=diff){
            if(arr_yak[index]==diff){
                return false;
            }
            index++;
        }
    
        while(index>0){ 
            //index가 다 될 까지 체크해야 하므로 초기화
            stack[++top] = --index; //배열에 수행해야할 index를 넣는다
            //cout<<"top while전 "<<top<<endl;
            d = diff;
            //cout<<"index : "<<index<<endl;
            while(top!=-1){ //stack이 비어있지 않으면
                i = stack[top--];   //하나 뺌
                //cout<<"top while안 i에 대입 "<<top<<endl;
                if(i<0) break;  //모두 둘러보았으면 넘긴다
    
                value = d - arr_yak[i]; //차이를 본다
                //cout<<"value : "<<d<<" - "<<arr_yak[i]<<" = "<<value<<endl;
                if(!value) return false;
    
                if(value>0){    //차이가 0보다 크면
                    d = value;  //차이를 덮어씌운다
                }
    
                stack[++top] = i - 1;
                //cout<<"top while안 i추가 "<<top<<endl;
            }
            //index--;  //얘보다 한단계 밑의 index 접근
            //cout<<"top while후 "<<top<<endl;
            //cout<<"----------------------------"<<endl;
        }
    
        delete []stack;
        return true;    //끝까지 가봐도 조합을 만들 수가 없으면
    }
    

    8년 전
2개의 댓글이 있습니다.
  • seico75
    seico75

    number 가 240 라고 하며 sum 은 504 가 될꺼 같고 diff 는 264 가 되겠네요. arr_yak 안의 최대수는 120, 자신의 수가 들어간다고 해도 240이므로 diff 보다는 작으니
    아래 루프는 의도한 범위를 벗어날 것이고 나머지 부분들이 쓰레기 값으로 0이 들어 있다고 하면 200 을 넘어서 메모리 치고 나갈 것 같네요.

    while(arr_yak[index]<=diff){
    if(arr_yak[index]==diff){
    return false;
    }
    index++;
    }


    8년 전 link
  • 빠비
    빠비

    제가 루프 넘어가는 수를 예상하지 못했었네요ㅠㅠ 정말 감사합니다


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