[알고스팟] PICNIC - 소풍 (C++)

문제

https://www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

풀이

고등학교 확률과 통계 시간에 뭔가 많이 볼 듯한 문제였다.

모든 경우의 수를 확인하는 Burute Force방법으로 해결하면 된다.

 

이차원 배열인

bool partnerBoard[45][45]    //45인 이유는 최대의 짝의 경우 수가 (10*9)/2이기 때문

에 서로의 친구 여부를 담아둔다.

 

그 후에는 기저 사례로 짝지어진 수가 전체 학생 수의 반인 경우(모든 짝이 지어진 경우) totalPairNum를 +1 해주는 재귀 함수를 호출한다.

 

재귀함수 FindPairUpNum는 학생의 번호인 idx를 받아와 만약 아직 짝을 지을 수 있는 경우 partnerBoar에서 짝을 찾은 후 isPosMatch를 false로 바꿔준 후 FindPairUpNum(idx+1,matchedCoupleNum+1)를 재귀 호출한다.

 

idx를  +1 해주어 다음 번호의 학생을 짝을 지어주고 지어진 짝의 수를 +1 해주는 구조이다.

여기서 짝을 찾는 반복문이 idx +1부터 시작하여 찾는 이유는 idx보다 낮은 번호의 학생들은 이미 재귀 호출을 거치며 짝짓기(?)를 완료한 상태이기 때문이다.

 

만약 isPosMatch가 false인 (이미 짝이 지어진 학생) 경우 그대로 다음 재귀를 호출한다.

 

코드