자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기

1. 문제

 

1947번: 선물 전달 (acmicpc.net)

1947번: 선물 전달

 

2. 풀이

 

PS를 위한 수학 - 교란 순열(완전순열) - 와 이게 에러가 뜨네 (mjstudio.net)

PS를 위한 수학 - 교란 순열(완전순열)

 

비가 오는 날에 n명의 사람이 자기의 우산을 쓰고 한 건물에 모여있다.

 

모두 동시에 집에 가려고 다시 우산을 쓰고 나가려는데, 자신의 우산을 사용하지 않는 경우의 수는?

 

n개의 물건을 n명의 사람에게 다시 분배하는데, 자기 물건을 다시 갖지 않는 경우의 수를 교란순열(완전순열, derangement)라고 부른다

 

점화식이 유명한데 (고등학교때부터..)

 

n = 0인 경우 생각할 필요도 없이 $a_{0} = 0$ 

 

n = 1인 경우 자기 자신 것만 가지게 되므로 $a_{1} = 0$

 

n = 2인 경우 서로 남의 것만 가지면 되므로 $a_{2} = 1$

 

$n \geq 3$인 경우, $i$번째 사람이 $j$번째 사람의 물건을 가져갔다고 가정하자.

 

$j$번째 사람이 $i$번째 사람의 물건을 가져갔다면,

 

$i,j$ 2명의 사람은 물건을 가져갔으므로 나머지 n-2명의 사람이 자기 것을 가져가지 않는 경우의 수는 $a_{n-2}$

 

이번엔 $j$번째 사람이 $i$번째 사람의 물건을 가져가지 않았다면, $i$번째 사람 1명만 결정되었고,

 

나머지 n-1명이 자기 것을 가져가지 않는 경우의 수는 $a_{n-1}$

 

즉, $i$번째 사람이 $j$번째 사람의 물건을 선택했을때 나타나는 경우의 수는 $a_{n-1}+a_{n-2}$

 

그런데 $j$로 가능한 경우는 $i$를 제외한 n-1가지이므로... 전체 경우의 수는 $(n-1)(a_{n-1} + a_{n-2})$

 

그래서 일반적으로..

 

$$a_{0} = a_{1} = 0, a_{2} = 1, a_{n} = (n-1)(a_{n-1} + a_{n-2}), n \geq 3$$

 

그러면 간단한 다이나믹 프로그래밍으로 문제를 해결할 수 있다

 

mod = 1000000000

n = int(input())

dp = [0]*(n+1)

if n >= 2:
    
    dp[2] = 1

for i in range(3,n+1):

    dp[i] = (i-1)*(dp[i-1]+dp[i-2])
    dp[i] %= mod

print(dp[n] % mod)