[Python] 10978번 기숙사 재배정

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

10978번: 기숙사 재배정

---

 

23/12/08

 

 

단순 교란 순열 문제이다. 알면 매우 쉽게 해결할 수 있다.

---

 

문제 접근 방식:

 

 

그냥 문제를 보면 교란 순열의 개수를 구하는 것과 같음을 알 수 있다.

 

교란 순열에 대한 간략한 설명은 다음 링크를 참고하자.

 

https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4

완전순열 - 위키백과, 우리 모두의 백과사전

 

교란 순열은 어떤 순열이 자기 자신으로 가는 원소가 단 하나라도 존재하지 않는다면, 그 순열을 교란 순열, 혹은 완전 순열이라고 부른다.

 

이 문제의 상황이 딱 그 상황이다.

 

$n$번째 교란 순열의 항을 $D_n$이라고 한다면, 교란 순열의 점화식은 다음과 같이 나온다.

 

$$D_n = (n-1)(D_{n-1} + D_{n-2})$$

 

그 이유는 다음과 같다. 어떤 교란 순열 $\sigma : (1, \cdots, n) \rightarrow (1, \cdots, n)$이 있다고 하자. 

 

$1$은 어떤 임의의 숫자 $k$로 간다고 하면, 우리는 두 가지 경우로 나눌 수 있다.

 

1. 임의의 숫자 $k$가 $1$로 가는 경우.

 

즉, $1$과 $k$는 $k$와 $1$로 간다. 이 경우 나머지 숫자들은 $n-2$개가 존재하므로 이 경우는 $D_{n-2}$와 동일하다.

 

2. 임의의 숫자 $k$가 $1$로 가지 않는 경우.

 

즉, 남은 $2$부터 $n$까지의 숫자들 중, $k$는 절대로 $1$로 가지 않으므로, 우리는 $k$를 $1$로 동일 시 할 수 있다. 따라서 이 경우는 $D_{n-1}$과 같다.

 

이 두 가지 경우 모두 $1$이 $2$부터 $n$까지 갈 수 있으므로 총 $n-1$가지가 나오므로 위와 같은 점화식이 나옴을 확인할 수 있다.

 

따라서 이 점화식을 그대로 구현하면 끝이다.

 

---

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

# 10978번 기숙사 재배정
# 교란 순열
D = [0 for _ in range(30)]
D[2] = 1
for i in range(3, 30):
    D[i] = (i-1)*(D[i-1] + D[i-2])
for _ in range(int(input())):
    print(D[int(input())])