Baekjoon 31474: 양갈래 짝 맞추기

문제 설명

• 문제 링크
• Algorithm: Mathematics, Combinatorics
• 난이도: Silver 4 ('24. 8. 28.)
• 출처: 랜덤 마라톤 코스 13 C번

풀이

• 조건1: 한 테이블에 2명이 앉을 수 있다.
• 조건2: 좌석과 테이블 순서는 중요하지 않다.
• 예제 2

  n = 4
  (ab), (cd)
  (ac), (bd)
  (ad), (bc)

• 가정1: 순서가 상관 없으니 a를 무조건 첫번째 테이블에 앉힌다고 가정하자
• 추론1: 첫번째 테이블에 앉을 수 있는 경우의 수는 $(n-1)$개이다.
  • a 이외의 인원들이 a와 같이 앉는경우
• 추론2: 두번째 테이블에 앉을 수 있는 경우의 수는 $(n-3)$개이다.
• 결론: $ \prod_{i=1}^{\frac{N}{2}}{N - (2i - 1)}$

코드

// Baekjoon31474.cpp
#include <iostream>

using namespace std;

using ll = long long;

int main(void) {
    int n;
    cin >> n;

    ll ans = 1LL;
    for (int i = 1; i <= n; i += 2)
        ans *= n - i;

    cout << ans << '\n';

    return 0;
}

잡담