[Python] 2682번 최대 사이클 1

https://www.acmicpc.net/problem/2682

2682번: 최대 사이클 1

---

 

24/03/21

 

 

순열 사이클 분할과 조합론적 지식을 활용한 문제이다.

---

 

문제 접근 방식:

 

 

어떤 순열 $P$의 최대 사이클 1의 값이 $1$이라면, $1$ 혼자서만 사이클을 생성하고, 나머지 $2$부터 $n$까지의 수들은 아무렇게 배치해도 상관없으므로, $(n-1)!$의 가짓수가 나온다.

 

$P$의 최대 사이클 1의 값이 $2$라면, $1$과 $2$는 서로 하나의 사이클로 묶여 있어야 하고, 나머지 $3$부터 $n$까지의 수들은 이 사이클과는 관련이 없으므로, $(n-2)!$의 가짓수가 나온다.

 

$P$의 최대 사이클 1의 값이 $3$이라면, $1$과 $3$은 서로 하나의 사이클로 묶여 있어야 한다.

 

$2$가 이 사이클에 포함이 되어있다면, $1, 2, 3$은 하나의 사이클이고 그 경우의 수는 $2!$이다. 또한 나머지 $(n-3)$개의 수들은 아무렇게 배치할 수 있으므로 $(n-3)!$이다. 따라서 $2! \times (n-3)!$가지가 나온다.

 

$2$가 이 사이클에 포함이 되어있지 않다면, $1, 3$이 하나의 사이클을 이루고, 나머지 $(n-2)$개의 수들은 아무렇게 배치할 수 있으므로 $(n-2)!$이다. 따라서 $(n-2)!$가지가 나온다.

 

따라서 $(n-2)! + 2! \times (n-3)!$가지가 나온다.

 

$P$의 최대 사이클 1의 값이 $4$라면 $1$과 $4$는 서로 하나의 사이클 $c$로 묶여 있어야 한다.

 

$c$의 크기가 $2$라면 나머지 수 $(n-2)$개를 아무렇게 배치하는 경우의 수와 같으므로, $(n-2)!$가지가 된다.

 

$c$의 크기가 $3$이라면 $2$또는 $3$중 하나를 선택하여 $c$를 이룬 뒤, $c$를 배열하는 경우의 수 $2!$를 곱하고, 나머지 수 $(n-3)$개를 아무렇게 배치할 수 있으므로 $(n-3)!$을 곱하여 ${2 \choose 1} \times 2! \times (n-3)!$가지가 된다.

 

$c$의 크기가 $4$라면 $2$또는 $3$중 두 개를 선택하여 $c$를 이룬 뒤, $c$를 배열하는 경우의 수 $3!$을 곱하고, 나머지 수 $(n-4)$개를 아무렇게 배치할 수 있으므로 $(n-4)!$을 곱하여 ${2 \choose 2} \times 3! \times (n-4)!$가지가 된다.

 

이를 모두 더하면 $(n-2)! + {2 \choose 1} \times 2! \times (n-3)! + {2 \choose 2} \times 3! \times (n-4)!$가지가 나온다.

 

따라서 이 과정을 일반화 하면 다음과 같은 수식으로 표현할 수 있다.

 

$$\sum_{i=0}^{k-2} ({{k-2} \choose i} \cdot (i+1)! \cdot (n-2-i)!)$$

 

이를 그대로 구현하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 2682번 최대 사이클 1
# 순열 사이클 분할, 조합론
'''
접근 방법:
1과 1이라면? (n-1)!
1과 2라면? (n-2)!
1과 3이라면? (n-2)! + 1C1*2!*(n-3)!
1과 4라면? (n-2)! + 2C1*2!*(n-3)! + 2C2*3!*(n-4)!
'''
import sys
input = sys.stdin.readline
from math import factorial, comb

T = int(input())
ans = []
for _ in range(T):
    N, K = map(int, input().split())
    if K == 1:
        ans.append(factorial(N-1))
    elif K == 2:
        ans.append(factorial(N-2))
    else:
        a = factorial(N-2)
        for i in range(1, K-1):
            a += comb(K-2, i)*factorial(i+1)*factorial(N-2-i)
        ans.append(a)
print(*ans, sep='\n')