알고스팟- [PICNIC] 문제 next_permutation으로 접근

예전에도 한번 풀어봤던 문제이다. 방학때 공부하는 책 한권을 완성하기 위해 다시 풀어보는 과정중에 next_permutation을 사용하여 접근을 해보았다.

#include<iostream>

//#include <stdio.h>

#include<string.h>

#include<vector>

#include<algorithm>

using namespace std;

int arr[56];

int answer;

int stuNum;

int setNum;

bool gett[56];

vector<int> v;

vector<int>::iterator iter;

int check(int a){

    for(int i=0;i<setNum*2;i++){

        if(((v.at(a)*10+v.at(a+1))==arr[i]||((v.at(a)+10*v.at(a+1))==arr[i]))){

            if((gett[i]!=false)){

                gett[i] = false;

                if(a == stuNum-2){

                    answer++;

                    memset(gett,true,sizeof(gett));

                    return 0;

                }

                else{

                    check(a+2);

                }

                gett[i] = true;

            }else{

                return 0;

            }

        }

    }

    return 0;

}

int main(){

    int testCase;

    cin >> testCase;

    //scanf("%d",&testCase);

    

    // next_permutation 쓸꺼임

    while(testCase--){

        

        answer =0;

        memset(gett,true,sizeof(gett));

        

        cin >> stuNum >> setNum;

        //scanf("%d %d" , &stuNum,&setNum);

        

        for(int i=0;i<stuNum;i++){

            v.push_back(i);

        }

        for(int i=0;i<setNum;i++){

            int a,b;

            cin >> a >> b;

            //scanf("%d %d",&a,&b);

            if(a>b){

                arr[i] = b*10+a;

            }else{

                arr[i] = a*10+b;

            }

        }               //입력 다함

        do{

            check(0);

        }while(next_permutation(v.begin(), v.end()));

       int useNum=1;

       for(int i=1;i<=stuNum/2;i++){

            useNum = useNum*2*i;

        }

        //printf("%d\n" , (answer/useNum));

        cout << answer/useNum << endl;

               

    }

}

윗 부분은 재귀함수를 구현 한 것이다.

근데 ... 해결하지 못한 문제가 있다 ....

1) 어디선가 초기화 문제가 발생하고 있다. 각각의 case 에 대해 입력을 주면 답이 나오는데 연속해서 입력을 하면 정답이 잘 출력되지 않는다.

2) 그래도 한번 제출 해보았는데 시간초과 ... 어디서 시간초과가 나는지를 모르겠다 ...

좀더 생각하고 접근해보도록 하자.