ALLERGY 비트로 코드 작성했는데 안됩니다.

  • jja08111
    jja08111

    제가 비트를 이용하여 코드를 작성했습니다.

    책과 유사하지만 비트맵을 이용하였다는 부분만 다릅니다.

    이를 위해서 canEat에는 i번 친구가 먹을 수 있는 음식들의 집합을 비트로 표현했고 eaters도 마찬가지 입니다.

    예제는 맞게 출력되지만 제출해보니 오답으로 나옵니다.

    어느 부분이 틀렸는지 도저히 감을 못잡아서 질문드립니다.

    #include <iostream>
    #include <vector>
    #include <string>
    #include <map>
    #include <algorithm>
    using namespace std;
    
    int n,m;
    //canEat: i번 친구가 먹을 수 있는 음식의 집합
    //eaters: i번 음식을 먹을수 있는 친구들의 집합
    //bit로 표현
    long long int canEat[50], eaters[50];
    int best;
    
    void init()
    {
        cin>>n>>m;
    
        map<string,int> index;
        for(int i=0;i<n;++i)
        {
            string name;
            cin>>name;
            index[name]=i;
        }
        //make canEat, eaters
        for(int i=0;i<50;++i)
            canEat[i]=eaters[i]=0;
        for(int i=0;i<m;++i)
        {
            int eatersNum;
            cin>>eatersNum;
    
            for(int j=0;j<eatersNum;++j)
            {
                string name;
                cin>>name;
    
                eaters[i]|=(1<<index[name]);
                canEat[index[name]]|=(1<<i);
            }
        }
    }
    
    void convertIndex(long long int& input)
    {
        int ret=0, num=input;
        while(num>1)
        {
            num/=2;
            ++ret;
        }
        input=ret;
    }
    
    void search(long long int edible, int chosen)
    {
        if(chosen>=best)
            return;
        //기저사례 : 전부 먹을 음식이 있는 경우
        if(edible==((1<<n)-1))
        {
            best=chosen;
            return;
        }
        //아직 먹을 음식이 없는 친구를 찾음
        long long int first=(~edible&(edible+1));
        convertIndex(first);
    
        //first친구가 먹을 수 있는 음식을 찾음
        for(int food=0;food<m;++food)
            if(canEat[first]&(1<<food))
                search(edible|eaters[food],chosen+1);
    }
    
    int main()
    {
        int testCase;
        cin>>testCase;
        while(testCase--)
        {
            init();
            best=m;
            search(0,0);
            cout<<best<<endl;
        }
    
        return 0;
    }
    

    4달 전
2개의 댓글이 있습니다.
  • jja08111
    jja08111

    아래부분 선언시 int형 말고 long long형으로 선언하니 성공했습니다.

    map<string,long long> index;
    

    4달 전 link
  • jja08111
    jja08111

    추가로 비트 연산시 1<<food 을 1LL<<food 로 변경해야 했습니다.


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