티스토리 뷰

Coding Test/알고스팟

[C++] 알고스팟/완전탐색 - 소풍

Junchoi 2020. 1. 10. 20:24

문제 링크

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

 

algospot.com :: PICNIC

소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요

www.algospot.com

 

재귀 호출을 사용해서 짝이 가능해지는 경우의 수를 모두 찾아가야합니다.

이 때 짝의 순서는 상관이 없기 때문에 같은 짝의 다른 순서들을 중복으로 카운트하지 않도록 하기 위해 짝이 지어지지 않은 번호가 가장 빠른 학생부터 항상 먼저 시작해야 합니다.

 

두 번째 예제 입력의 경우 4명의 친구가 서로 다른 모든 친구와 짝이 되어도 괜찮은 경우입니다.

 

 

구현 코드

 

'Coding Test > 알고스팟' 카테고리의 다른 글

[C++] 알고스팟/완전탐색 - Synchronizing Clocks  (0) 2020.01.18
[C++] 알고스팟/완전탐색 - 게임판 덮기  (0) 2020.01.11
[C++] 알고스팟/유클리드 - 마법의 약  (0) 2020.01.08
[C++] 알고스팟/에라토스테네스의 체 - 비밀번호486  (0) 2020.01.06
[C++] 알고스팟/삼분검색 - 꽃가루 화석  (0) 2020.01.05