[BOJ 백준] 31474 양갈래 짝 맞추기 (C++ 풀이)

링크

https://www.acmicpc.net/problem/31474

31474번: 양갈래 짝 맞추기

 

풀이

 

백준 31474번 문제 양갈래 짝 맞추기는 조합론으로 풀 수 있는 문제입니다. N은 총 인원의 수로 짝수로 주어지고, 테이블에 앉히는 경우의 수를 구하는 문제인데요. 두 가지 조건이 있습니다.

 

1. 한 테이블에서는 좌석 구분이 없다. (마치 아무 것도 없는 완벽한 원형 테이블에 마주 앉아있는 두 사람처럼 한 테이블에 A B가 앉든 B A가 앉든 같은 경우라는 뜻입니다.)

 

2. 각각의 테이블 또한 구분하지 않는다. 이는 테이블에 앉히는 순서를 고려하지 않는다는 것입니다.

 

예시

일단 N이 8, 즉 총 인원이 8명이라고 가정하고 예시를 들어보겠습니다.

8C2

8명이 있고 이 중에 두 명을 뽑을 건데요, 1번 조건에 따라 뽑힌 순서는 상관 없다고 해볼게요. 이때 조합을 사용해 8C2라고 나타낼 수 있는데요. 계산은 8*7/2라고 해줄 수 있습니다. 8*7은 8명에서 한 명을, 남은 7명에서 한 명을 뽑는 경우의 수인데, 이때 겹치는 경우를 제외하기 위해 2로 나누어준 것입니다. (엄밀하게 말하면 2!로 나누어준 것)

 

따라서 먼저 순서를 고려해서 순열을 뽑아주고, 겹치는 경우로 나누어준 것이죠. 따라서 1번 조건은 사람을 뽑을 때 P(순열)대신 C(조합)를 이용하라는 조건입니다. 

 

8C2 * 6C2 * 4C2 * 2C2

8명 중에서 2명을 뽑았으니, 나머지 6명에서 2명을, 4명에서 2명을 마지막 2명을 뽑는다고 하면 이를 다음과 같이 나타낼 수 있는데요.

8C2 * 6C2 * 4C2 * 2C2

 

곱하기로 표현한 이유는 동시에 일어나는 사건이기 때문입니다. 시간차를 두고 뽑은 것 아닌가라고 생각할 수 있겠지만, 8명에서 2명을 뽑은 상태에서 2명을 더 뽑고 .. 이렇게 연속적으로 얽혀있죠. 이럴 때 확률론에서는 동시에 일어나는 사건으로 생각합니다.

 

8C2 * 6C2 * 4C2 * 2C2 / 4!

이제 2번 조건을 사용해야 하는데요. 위에서 사용한 조합은 두 명 = 한 쌍을 뽑을 때 순서를 고려하지 않는다는 것이기 때문에, 그 쌍들을 뽑는 순서가 생긴 걸 또 없애줘야 합니다.

 

예시에서 8명 중 처음 뽑힌 두 명이 A, B고 마지막으로 남은 2명이 C, D인 경우도 위 조합식에 존재하고, 처음에 C, D가 마지막에 A, B가 뽑힌 경우도 존재합니다. 뽑는 순서대로 테이블에 앉힌 셈인데, 이러면 가장 먼저 앉은 테이블부터 마지막에 앉은 테이블까지 테이블의 순서가 매겨집니다.

 

이 순서를 없애주기 위해서는 테이블을 순서대로 배치하는 경우의 수로 나눠주면 되는데, 이는 순열이고 모든 테이블에 앉기 때문에(다른 테이블을 쓰지 않기 때문에) 테이블 개수의 팩토리얼로 나누어주면 됩니다. 위와 같은 경우는 4P4 = 4!으로 나누어주면 되죠. 테이블 개수는 N/2개입니다.

 

반응형

 

일반화

위 예시를 일반화해보면 아래 식을 구할 수 있습니다. 총 인원이 N명일 때, 테이블에 앉히는 경우의 수는 다음과 같습니다.

NC2 * (N-2)C2 * (N-4)C2 * ... * 2C2 / (N/2)!

 

이를 반복문으로 구해서 출력하면 되고, 앞의 조합과 뒤의 팩토리얼을 따로 계산하게 되면 경우의 수가 정수 범위를 초과하기 때문에 한 for 문에 곱과 나누기를 적절히 섞어 정수 크기를 조절해줍니다. 코드 링크 남겨놓겠습니다.

 

코드

https://github.com/jaemin8852/BOJ/blob/master/31474_%EC%96%91%EA%B0%88%EB%9E%98%20%EC%A7%9D%20%EB%A7%9E%EC%B6%94%EA%B8%B0.cpp