[Algo] 백준 1947 선물 전달 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/1947

메모리 : 22144KB

시간 : 172ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        long[] dp = new long[1000001];
        dp[1] = 0;
        dp[2] = 1;
        int mod = 1000000000;
        for (int i = 3; i < 1000001; i++) {
            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2]) % mod) % mod;
        }
        System.out.print(dp[N]);
    }
}

풀이

고등학생 때 미적분 배우면서 많이 풀었던 문제입니다.

일반항 $D_n= \displaystyle n!\sum_{k=0}^{n}{(-1)^k \over k!}$

점화식 $Dn=(n−1)(D_{n−1}+D_{n−2})$

교란순열, 완전순열 혹은 서브팩토리얼이라고 불리네요. 새로운 지식!

1...n의 배열 중 n을 기준으로 보자.

n을 뽑아서 n이 입주할 수 있는 자리의 개수 = n-1

그리고 n에게 쫒겨난 어떤 수 x가 갈수있는 자리의 개수

• n과 어떤 수 x의 1대1 교환인 경우 : n자리에 x가 들어가고 x자리에 n이 들어가는 경우 이 두가지 숫자를 빼고 나머지 수를 나열할 수 있다. = $D_{n-2}$
• n을 어떤 수 x자리에 넣고, x는 또다른 어떤 수 y가 들어가는 경우 : n을 제외한 숫자를 가지고 나열하는 경우와 같다. $D_{n-1}$

이 두 사건은 동시에 일어나지 않기 때문에 확률을 더해준다.

결론 : n이 들어갈 수 있는 자리의 수 * n이 밀어낸 어떤 수 x가 어디에 들어가는지 경우의 수

dp로 풀기 때문에 $D_{n-1}$가 이미 자신의 선물을 자신이 뽑지 않은 -중복되지 않은- 경우의 수이기때문에 점화식이 가능하다.