[알고리즘 문제 해결 전략] 소풍 (ID : PICNIC)

1. 문제를 읽고 이해하기 학생을 2명씩 짝 지을 것이다 친구끼리만 짝을 지을 수 있다. 짝 지을 수 있는 경우의 수 구하기 2. 재정의 및 추상화 / 계획 세우기 brute force로 가능할 것 같다. 최대한 많이 살펴보는 가짓수로는 열 명의 학생이 친구인 것인데, 첫 번째 학생은 9명 중 한 명을 고르고 다음은 7명 중 한 명을 고르고 ... 9 * 7 * 5 * 3 * 1 = 945 이다...! 재귀함수를 이용하여 체크하며 3. 계획 검증하기 답의 수를 세는 재귀함수는 답의 수에 정비례하는데 가지치기하며 brute force로 찾아보면 최대 경우의 수가 9*7*5*3*1=945 이므로 현저히 낮음. 따라서 시간제한에 걸리지 않는다. (참고로 1초에 약 1억 번의 계산을 할 수 있다고 생각하면 된다..

원문링크 : [알고리즘 문제 해결 전략] 소풍 (ID : PICNIC)