PICNIC 질문입니다. akcytm #include <iostream> #include <fstream> using namespace std; class FriendSeq { private: int Flag; public: //Flag에 2의_Flag제곱을 더합니다. void SetFlag(int _Flag) { int temp=1; for(int i=0;i<_Flag;++i) temp*=2; Flag=Flag|temp; return; } //Flag에 2의_Flag제곱을 뺍합니다. void XorFlag(int _Flag) { int temp=1; for(int i=0;i<_Flag;++i) temp*=2; Flag=Flag^temp; return; } //Flag에 2의_Flag제곱이 있는지 체크합니다. int CheckFlag(int _Flag) { int temp=1; for(int i=0;i<_Flag;++i) temp*=2; return Flag&temp; } //Flag값 출력, 0으로 초기화 int OutFlag(){return Flag;} void Refresh(){Flag=0;}; }; int Tcase=0,Nstudent=0,Nseq=1,temp=0,result=0; int x[23],y[23];//이것은 Friend로 묶어진 친구들을 저장하기 위해 선언했습니다. FriendSeq z; void tr(int _x,int Size,int Level) { //Seq가 골라졌는지 확인. 골라졌으면 통과 if((z.CheckFlag(x[_x])>0)||(z.CheckFlag(y[_x])>0)) return; else { //마지막으로 선택하는거라면, 플래그에 추가할 필요 없음. if(Level==1) { ++result; return; } //안골라진거니까 플래그에 추가. z.SetFlag(x[_x]);z.SetFlag(y[_x]); } //제귀호출 for(int i=1;i<Size+1;++i) tr(_x+i,Size-i+1,Level-1); //종료되기전에, 추가했던 Seq 제거? z.XorFlag(x[_x]);z.XorFlag(y[_x]); return; } int main() { fstream fs; fs.open("input.txt",ios::in); fs>>Tcase; for(int k=0;k<Tcase;++k) { fs>>Nstudent;fs>>Nseq; temp=Nseq-(Nstudent/2)+1; for(int i=0;i<Nseq;++i) { fs>>x[i];fs>>y[i]; } for(int i=0;i<temp;++i) tr(i,temp-i,Nstudent/2); cout<<result<<endl; result=0; } return 0; } 우선 책에 나와있는 예제는 문제없이 다 출력됩니다. 제가 임의로 만든(사람의 수:8, 친구쌍의 수:10)입력값에도 문제없이 돌아갔습니다. 구현 메커니즘은, Recursion을 이용했습니다. 친구쌍이 중복되는게 없는지를 판별하기 위해 Logic Gate를 이용했습니다. 사람 번호에 따른 값을 0은 1, 1은 2, 2는 4, ... 으로 정한다음 OR, XOR연산을 이용했습니다. 오작동을 할 만한, 반례찾기가 참 힘드네요ㅠ 11년 전
9개의 댓글이 있습니다. JongMan 초기화 문제가 있네요. 11년 전 link akcytm 어떤 초기화 문제가 있나요 ㅠ? 11년 전 link JongMan 전역 변수가 여러 개 있으시죠? 한 케이스를 처리하고 나서 다음 케이스를 입력받을 때 이들이 잘 초기화되는지, 원하는 값을 갖고 있는지 눈여겨 한번 보세요. 11년 전 link JongMan 아니면 책에 있는 예제 입력을 여러 번 반복해서 넣어 보세요. A, B, C 세 개의 예제 입력이 있으면 ABCABC 이렇게 넣어 보시는거죠. 11년 전 link akcytm 그렇게 해봐도 결과는 잘 나옵니다ㅠ 아무래도 알고리즘이 틀렸나봐요. 11년 전 link kcm1700 아 그리고 이건 관계 없는 거기는 한데, int temp=1; for(int i=0;i<_Flag;++i) temp*=2; 이렇게 하실 필요 없이 1<<_Flag를 쓰시면 되어요. 11년 전 link JongMan 에구, 초기화 문제가 아니군요; 입력을 돌려보니 첫 몇개 빼고는 쭉 0이 나오길래 초기화 문제인줄 지레짐작했는데, 알고리즘에 문제가 있군요. 사죄의 의미로 코드를 제대로 뒤져보았습니다. 문제는 배열 크기입니다. 입력 크기는 최대 10이니, 10*9/2 = 최대 45개의 연결이 있는데 x, y 배열은 23개밖에 없군요. 문제 푸신 후에는 다른 사람 구현도 참조해서 더 간결하게 짜 보시는 것을 추천드릴께요~ 11년 전 link JongMan 본의 아니게 삽질하게 해드려서 죄송해요~ 11년 전 link akcytm 아아 감사합니다. 사죄의 의미라니요ㅠ 여러번 답변을 달아주셔서 정말 감사합니다. 코드를 고쳐보니 제대로 돌아가는군요. 상상치 못한곳에서 뻘짓을 했군요. 덕분에 많이 배워갑니다. 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
akcytm
우선 책에 나와있는 예제는 문제없이 다 출력됩니다.
제가 임의로 만든(사람의 수:8, 친구쌍의 수:10)입력값에도 문제없이
돌아갔습니다.
구현 메커니즘은, Recursion을 이용했습니다.
친구쌍이 중복되는게 없는지를 판별하기 위해 Logic Gate를 이용했습니다.
사람 번호에 따른 값을 0은 1, 1은 2, 2는 4, ...
으로 정한다음 OR, XOR연산을 이용했습니다.
오작동을 할 만한, 반례찾기가 참 힘드네요ㅠ
11년 전