importjava.util.Scanner;publicclassAllergy{staticint[]marker;staticint[]selectedIndex;staticint[][]Matrix;staticintminimum;staticintMin=Integer.MAX_VALUE;staticint[]test;publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Friendf;inttestCase=sc.nextInt();for(inti=0;i<testCase;i++){intnumOfFriends=sc.nextInt();// 친구수 입력받음intnumOfFoods=sc.nextInt();// 음식수 입력 받음f=newFriend(numOfFriends);Matrix=newint[numOfFoods][numOfFriends];// 즉 1행에 음식1 이있고 그거에대한 사람 o x 그런 마커가 있겟지 그런식으로 만듬.for(intj=0;j<numOfFriends;j++){f.addFriends(sc.next());}// 사람입력받음for(intj=0;j<numOfFoods;j++){// 음식에 관한 정보들을 입력받아야되intl=sc.nextInt();for(intk=0;k<l;k++){Stringtemp=sc.next();inttemp1=f.rindex(temp);Matrix[j][temp1]=1;// 이로써 맵핑을 시켯다.}}minimum=0;// 최솟값저장을 위한marker=newint[numOfFriends];selectedIndex=newint[numOfFoods];while(true){for(intj=0;j<numOfFoods;j++){if(isPossible(j)){Mapping(j,marker);compare(j);}}break;}System.out.println(minimum);}}// main함수의 끝 end of mainpublicstaticbooleancheck(){for(inti=0;i<marker.length;i++){if(marker[i]!=1){returnfalse;}}returntrue;}publicstaticvoidcompare(intk){for(inti=0;true;i++){if(i>minimum-1){break;}test=newint[Matrix[0].length];booleanx=true;for(intr=0;r<minimum;r++){if(r==i){continue;}else{Mapping(selectedIndex[r],test);}}Mapping(k,test);for(intj=0;j<test.length;j++){if(test[j]!=marker[j]){x=false;break;}}if(x){System.arraycopy(selectedIndex,0,selectedIndex,0,i);System.arraycopy(selectedIndex,i+1,selectedIndex,i,minimum-(i+1));minimum--;i--;}}test=newint[Matrix[0].length];for(inti=0;i<minimum;i++){Mapping(selectedIndex[i],test);}booleancheck=false;for(inti=0;i<test.length;i++){if(marker[i]==1&&test[i]!=1){check=true;}}if(check){selectedIndex[minimum]=k;minimum++;}}publicstaticvoidMapping(intk,int[]target){for(inti=0;i<marker.length;i++){if(Matrix[k][i]==1){target[i]=1;}}}publicstaticbooleanisPossible(intk){// matrix의 행.//현재 선택된 행의 값들이 selectedIndex안에 있는 값들중에 혹시 포함되는게 있으면.//false로 가면되지..for(inti=0;i<minimum;i++){if(isAinB(k,i)){returnfalse;}}returntrue;}publicstaticbooleanisAinB(inta,intb){//a와 b둘다 행이야.//a가 b안에 들있으면 true;for(inti=0;i<Matrix[0].length;i++){if(Matrix[a][i]==1&&Matrix[b][i]!=1){returnfalse;}}returntrue;}publicstaticclassFriend{String[]FriendsList;intcount;publicFriend(intnum){FriendsList=newString[num];count=0;}publicvoidaddFriends(Stringa){FriendsList[count]=a;count++;}publicintrindex(Stringa){intk=-1;for(inti=0;i<FriendsList.length;i++){if(FriendsList[i].equals(a)){k=i;break;}}returnk;}}}
9년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
ycyc02
알러지 문제에서 왠만한 답들은 맞는것 같은데
오답이라고 하니까
어떤경우에 오답인지 도저히 생각이 안납니다 ㅠㅠ..
어떤경우에 오답이 생기는지 worstCase 에대해서
알려주시면 감사하겠습니다,,,,
9년 전