[BOJ] 20443. 배드민턴 대회

Problem

BOJ 20443. 배드민턴 대회

$N$명의 참가자가 있다.

1. 참가자 수를 4의 배수로 맞추기 위해, $0 \sim 3$명을 무작위로 추첨에서 제외한다.
2. 남은 참가자들은 자신의 번호가 아닌 번호표를 뽑아야 한다. (자기 자신과 매칭되지 않음)

모든 경우의 수를 $1,000,000,007$로 나눈 나머지를 구하시오.

• $1 \le N \le 100$

Input:
4

Output:
9

(Explanation: 4 is divisible by 4. k=0. M=4. Derangement D4 = 9.)

---

Initial Thought (Failed)

단순히 순열(Permutation)을 생성해서 arr[i] != i 인지 확인하면 될까요?

• 순열의 개수: $N!$.
• $N=100$이면 $100!$은 계산 불가능한 큰 수입니다.

따라서 완전 순열 (Derangement) 공식을 사용해야 합니다.

---

Key Insight

이 문제는 두 단계로 나눌 수 있습니다.

1. Selection: $N$명 중 조건을 만족하는 $M$명을 선택하는 방법의 수 $\binom{N}{M}$.
   • $(N-k) \pmod 4 = 0$ 인 $k \in {0, 1, 2, 3}$를 찾습니다. $M = N-k$.
2. Derangement: 선택된 $M$명이 모두 자기 자신이 아닌 번호를 뽑는 경우의 수 $D_M$.

\[\text{Answer} = \binom{N}{M} \times D_M\]

완전 순열(교란 순열) 점화식: \(D_n = (n-1)(D_{n-1} + D_{n-2})\)

---

Step-by-Step Analysis

$N=5$일 때:

1. Remainder check: $5 \pmod 4 = 1$. 따라서 $k=1$명을 제외해야 함. 남은 인원 $M=4$.
2. Combination: 5명 중 4명 선택 $\binom{5}{4} = 5$.
3. Derangement: $D_4 = 9$.
   • $D_1 = 0$
   • $D_2 = 1$ (21)
   • $D_3 = 2$ (231, 312)
   • $D_4 = 9$ (2143, 2341, 2413 …)
4. Result: $5 \times 9 = 45$.

graph TD
    A["Start: N"] --> B{"Calculate Remainder R = N % 4"}
    B --> C["Exclude k = R people"]
    C --> D["Target Size M = N - k"]
    D --> E["Calculate Comb(N, M)"]
    D --> F["Calculate Derangement D_M"]
    E --> G["Multiply"]
    F --> G
    G --> H["Result % MOD"]

---

Solution

import sys

# 입력 받기
input = sys.stdin.readline
N = int(input())
MOD = 1000000007

# 1. DP로 교란 순열(Derangement) 미리 계산
# D[n] = (n-1) * (D[n-1] + D[n-2])
D = [0] * (N + 1)
if N >= 2:
    D[2] = 1

for i in range(3, N + 1):
    D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % MOD
# end for

# 2. 조합(Combination) 계산 함수
# N이 작으므로(100) 팩토리얼 없이 파스칼 삼각형이나 단순 반복문도 가능하지만,
# 여기서는 큰 수 계산을 고려하지 않아도 되므로 직접 계산 (모듈러 주의)
def combination(n, r):
    if r < 0 or r > n:
        return 0
    num = 1
    den = 1
    for i in range(r):
        num = num * (n - i)
        den = den * (i + 1)
    return (num // den) % MOD  # 나눗셈이 딱 떨어지므로 정수 나눗셈 후 모듈러
# end def

# 3. 정답 계산
remainder = N % 4
M = N - remainder  # 4의 배수가 되는 최대 인원

# 조합 * 교란순열
comb_val = combination(N, M)
derange_val = D[M]

print((comb_val * derange_val) % MOD)

---

Complexity

• Time Complexity: $O(N)$
  • $D_N$ 테이블 채우기: $O(N)$.
  • 조합 계산: $O(N)$ (혹은 $O(1)$ since $k \le 3$).
• Space Complexity: $O(N)$
  • $D$ 배열.

---

Key Takeaways

Point	Description
Derangement ($!n$)	모든 원소가 자기 위치에 있지 않은 순열의 개수
Recurrence	$D_n = (n-1)(D_{n-1} + D_{n-2})$
Modular Arithmetic	중간 계산 과정에서도 나머지 연산을 적용하여 오버플로우 방지