[알고스팟] PICNIC - 소풍 (C++)
문제
https://www.algospot.com/judge/problem/read/PICNIC
algospot.com :: PICNIC
소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로
www.algospot.com
풀이
고등학교 확률과 통계 시간에 뭔가 많이 볼 듯한 문제였다.
모든 경우의 수를 확인하는 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인 (이미 짝이 지어진 학생) 경우 그대로 다음 재귀를 호출한다.