백준 - 선물 전달 (1947)

let MOD = 1000000000
let N = Int(readLine()!)!
var dp = Array(repeating: 0, count: N + 1)

// dp 테이블 초기화
if N > 1 {
    dp[2] = 1
}

// dp 테이블 채우기
for i in stride(from: 3, through: N, by: 1) {
    dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
}

print(dp[N])

완전순열의 점화식을 사용해서 푸는 문제이다.