이를 위해서 canEat에는 i번 친구가 먹을 수 있는 음식들의 집합을 비트로 표현했고 eaters도 마찬가지 입니다.
예제는 맞게 출력되지만 제출해보니 오답으로 나옵니다.
어느 부분이 틀렸는지 도저히 감을 못잡아서 질문드립니다.
#include <iostream>#include <vector>#include <string>#include <map>#include <algorithm>usingnamespacestd;intn,m;//canEat: i번 친구가 먹을 수 있는 음식의 집합//eaters: i번 음식을 먹을수 있는 친구들의 집합//bit로 표현longlongintcanEat[50],eaters[50];intbest;voidinit(){cin>>n>>m;map<string,int>index;for(inti=0;i<n;++i){stringname;cin>>name;index[name]=i;}//make canEat, eatersfor(inti=0;i<50;++i)canEat[i]=eaters[i]=0;for(inti=0;i<m;++i){inteatersNum;cin>>eatersNum;for(intj=0;j<eatersNum;++j){stringname;cin>>name;eaters[i]|=(1<<index[name]);canEat[index[name]]|=(1<<i);}}}voidconvertIndex(longlongint&input){intret=0,num=input;while(num>1){num/=2;++ret;}input=ret;}voidsearch(longlongintedible,intchosen){if(chosen>=best)return;//기저사례 : 전부 먹을 음식이 있는 경우if(edible==((1<<n)-1)){best=chosen;return;}//아직 먹을 음식이 없는 친구를 찾음longlongintfirst=(~edible&(edible+1));convertIndex(first);//first친구가 먹을 수 있는 음식을 찾음for(intfood=0;food<m;++food)if(canEat[first]&(1<<food))search(edible|eaters[food],chosen+1);}intmain(){inttestCase;cin>>testCase;while(testCase--){init();best=m;search(0,0);cout<<best<<endl;}return0;}
jja08111
제가 비트를 이용하여 코드를 작성했습니다.
책과 유사하지만 비트맵을 이용하였다는 부분만 다릅니다.
이를 위해서 canEat에는 i번 친구가 먹을 수 있는 음식들의 집합을 비트로 표현했고 eaters도 마찬가지 입니다.
예제는 맞게 출력되지만 제출해보니 오답으로 나옵니다.
어느 부분이 틀렸는지 도저히 감을 못잡아서 질문드립니다.
4년 전