[Algospot] PICNIC
문제
https://www.algospot.com/judge/problem/read/PICNIC
#include <iostream>
#include <cstring>
using namespace std;
int cnt=0;
int isFriend[11][11];
bool isPair[11];
void findPair(int num){
int sum=0;
for(int k=0; k<num; k++){
sum += isPair[k];
}
if (sum == num){
cnt++;
return;
}
for(int i=0; i<num; i++){
for(int j=0; j<num; j++){
if(!isPair[i] && !isPair[j] && isFriend[i][j]){
isPair[i] = isPair[j] = true;
findPair(num);
isPair[i] = isPair[j] = false;
}
}
}
}
int main(){
int test, num, pair;
cin >> test;
while (test--){
cnt = 0;
cin >> num >> pair;
memset(isFriend, 0, sizeof(isFriend));
memset(isPair, 0, sizeof(isPair));
while(pair--){
int x,y;
cin >> x >> y;
isFriend[x][y] = 1;
}
findPair(num);
int i = num / 2;
while (i){
cnt /= i;
i--;
}
cout << cnt << endl;
}
}
처음에 중복을 해결해주지 않아 무시무시한 수가 나왔다.
책에서는
isFriend[x][y] = 1;
isFriend[y][x] = 1;
다음과 같이 했지만 이럴 경우 짝(1,2)와 짝(2,1) 을 다른 경우로 취급하기에 한번만 값을 넣었다.
또한 [(1,2), (3,4)], [(3,4), (1,2)] 처럼 중복이 되므로
결과를 (전체학생수/2)!로 나누어 주어야한다
Author And Source
이 문제에 관하여([Algospot] PICNIC), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lacram/Algospot-PICNIC저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)