PICNIC 문제인제 제가 제출하는 방법이 잘못된건지 그냥 오답이라고 나오는데 시간도 짧게 걸리는거 같고 답도 잘 나오거든요;;;;

  • ghkd0205
    ghkd0205
    #include <iostream>
    using namespace std;
    
    int testCase; //테스트 케이스 수
    int sCount; // 학생의 수
    int fCount; // 친구쌍의 수
    bool areFriends[10][10];
    // taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
    int countPairings(bool taken[10]){
        //남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
        int firstFree = -1;
        for(int i = 0; i < sCount; ++i) {
            if(!taken[i]) {
                firstFree = i;
                break;
            }
        }
        //기저 사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
        if(firstFree == -1) return 1;
        int ret = 0;
        // 이 학생과 짝지을 학생을 결정한다.
        for(int pairWith = firstFree+1; pairWith < sCount; ++pairWith){
            if(!taken[pairWith] && areFriends[firstFree][pairWith]){
                taken[firstFree] = taken[pairWith] = true;
                ret += countPairings(taken);
                taken[firstFree] = taken[pairWith] = false;
            }
        }
        return ret;
    }
    
    int main(void)
    {
    
        int x, y;
        bool taken[10];
        int i, tc;
    
        cin>>testCase;
    
        int * result = new int[testCase];
        tc = testCase;
        i=0;
        while(testCase >0){
            cin>>sCount;
            cin>>fCount;
            for(int i=0; i<fCount; ++i)
            {
    
                cin>>x>>y;
                areFriends[x][y] = true;
                areFriends[y][x] = true;
            }
            result[i] = countPairings(taken);
            testCase--;
            i++;
    
            for(int i=0; i<10; ++i)
                for(int j=0; j<10; j++)
                    areFriends[i][j] = false;
    
            for(int i=0; i<10; ++i)
                taken[i] = false;
        }
        for(int i=0; i<tc; ++i)
            cout<<result[i]<<endl;
    
        return 0;
    }
    

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

    C/C++에서 지역 변수는 항상 0/false로 초기화되지 않습니다. 이 점을 염두에 두고 다시 훑어보세요.


    9년 전 link
  • ghkd0205
    ghkd0205

    감사합니다 ㅎㅎ 간단한 부분에서 문제 였네요
    혹시 알고리즘 문제해결 전략 저자이신 구종만님 맞으신가요?
    혹시 맞다면 책 잘보고 열심히 공부하고 있습니다 ㅎㅎ


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