[1947] 선물 전달하기 (완전 순열, 교란 순열)

1947번: 선물 전달

 

분석

완전 순열 : n개의 원소가 모두 자기 자신이 아닌 값으로 배정되는 순열 (모든 원소의 위치를 바꾸는 순열)

A가 B에게 선물을 줬다고 가정

1. B도 A에게 선물을 줬을 때 (양방향 교환)
: N명 중 2명이 교환을 완료했으므로 남은 경우의 수는 D[N-2]

2. B는 A가 아닌 다른 사람에게 선물을 선달할 때 (단방향 교환)
: N명 중 B만 받은 선물이 정해진 상태이므로 남은 학생은 N-1이며 경우의 수는 D[N-1]

 

풀이

n=int(input())
mod=1000000000
d=[0]*10000001
d[1]=0 # 혼자서는 선물을 교환할 수 없음
d[2]=1 # 2명일 경우에는 서로 교환하는 경우의 수만 존재

for i in range(3,n+1):
    d[i]=(i-1)*(d[i-1]+d[i-2]) %mod

print(d[n])

 

참고

교란순열(derangement)에 대하여