PICNIC문제 어떤경우가 오답인지 여쭙니다

  • rlarlvy153
    rlarlvy153

    간단한 코드설명

    match 함수로 size/2 를 depth에 넣고, 몇쌍을 검사해야하는지를 depth를 통해서
    재귀함수 몇층까지 내려갈지 검사합니다.

    check는 각 인자들이 학생을 의미하는데, 1이면 짝을 찾았단 의미이고
    최종깊이의 재귀함수 까지 갔을경우 짝을 못찾은 학생이 있을경우 실패의 0을,
    모두 짝을찾을경우 1을 리턴하여 sum에 더해줘서 경우의수 하나를 추가합니다.

    오답이 뜨기에 몇일을 들여다봤는데 오류케이스도 못만들어내겠고..
    어떤경우가 혹시 오답인지 도저히 떠오르지않아서 여쭙니다.

    글 읽어주셔서 감사합니다.

    #include <iostream>
    
    using namespace std;
    
    
    int is_success(int *check, int size){
    
        for (int i = 0; i<size; i++)
        if (check[i] != 1){
            delete[] check;
            return 0;
        }
        delete[] check;
        return 1;
    }
    
    
    int match(int depth, int *check, int index, int size, int **friends, int pairs){
        int sum = 0;
        int * temp_check = new int[size];
    
        //int *temp_check = new int[size];
    
        for (int i = 0; i<size; i++)
            temp_check[i] = check[i];
        temp_check[friends[index][0]] = temp_check[friends[index][1]] = 1;
    
        if (depth == 1)
            return is_success(temp_check, size);
    
        for (int i = 0; i<pairs; i++)
        if (i>index)
            sum += match(depth - 1, temp_check, i, size, friends, pairs);
    
        delete[] temp_check;
        return sum;
    }
    
    
    
    int main() {
        int count;
        cin >> count;
    
        while (count--){
            int size, pairs;
            int ans = 0;
            cin >> size >> pairs;
    
            int *check = new int[size];
            int **friends = new int*[pairs];
    
            for (int i = 0; i<pairs; i++)
                friends[i] = new int[2];
    
            for (int i = 0; i<pairs; i++)
            for (int j = 0; j<2; j++)
                cin >> friends[i][j];
    
            for (int i = 0; i<pairs; i++){
                ans += match(size / 2, check, i, size, friends, pairs);
            }
    
            cout << ans;
    
            for (int i = 0; i<pairs; i++)
                delete[] friends[i];
            delete[] friends;
            delete[] check;
        }//end while
    
        return 0;
    }
    

    9년 전
2개의 댓글이 있습니다.
  • Being
    Being

    얼핏 보기에는 check 객체의 내용이 제대로 초기화되지 않을 것 같네요.


    9년 전 link
  • rlarlvy153
    rlarlvy153

    끄흥.. 그래도 오답이군요 ㅠ


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