[백준] 1947번. 선물 전달(JAVA)

문제

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

---

풀이(28분)

import java.io.*;
import java.util.*;

class Main {
    static final int DIVIDER = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1_000_001];
        dp[1] = 0;
        dp[2] = 1; // 초기화

        for(int i = 3; i <= n; i++){
            dp[i] = (int)(((long)(i-1) * (long)(dp[i-1] + dp[i-2])) % DIVIDER);
        }

        System.out.println(dp[n]);
    }
}

---

문제 풀이 전략

 

점화식만 이해하면 되는 DP문제이다.

 

✅ 초기 접근

처음에는 다음과 같은 방식으로 문제를 해결하고자 했다:

5! - (5C5 x 1  + 5C4 x 0 + 5C3 x dp[2] + 5C2 x dp[3] + 5C1 x dp[4])

💡 아이디어

1. 일단 n명의 사람이 모두 선물을 나눠 갖는 경우의 수를 구한다.
2. 그중에서 자기 자신의 선물을 갖는 경우의 수를 제거한다.
3. 예를 들어, n명 중 n-2명만 자기 자신의 선물을 가지는 경우를 생각하고, 이를 끝까지 반복해서 제거한다.

하지만 이 방식은 시간 복잡도가 높아 계산량이 많고, 효율적이지 않다.
그래서 이 접근은 실제로 제출조차 하지 않고 포기했다.

---

📌 더 나은 점화식 발견

다음과 같은 점화식을 찾게 되었다:

점화식

D(n) = (n-1) * (D[n-1] + D[n-2])

---

🧠 점화식 유도 과정

1. n명 중 한 명 (예: 1번)이 자기 자신의 선물을 제외한 n - 1개 중 하나를 받는 경우의 수는 총 n - 1가지이다.
2. 이때 1번이 받은 선물의 주인을 k번이라고 하자.

경우 1: k번이 1번의 선물을 가져가는 경우

• 1번과 k번은 서로 교환한 셈.
• 이제 남은 n - 2명에 대해 전부 자기 선물이 아닌 경우의 수 = D(n - 2)

경우 2: k번이 1번의 선물을 가져가지 않는 경우

• 이제 k번은 1번의 선물을 제외한 나머지 중 하나를 골라야 한다.
• 이는 "n - 1명에 대한 derangement"와 동일한 문제가 된다 = D(n - 1)

즉, "k번이 자기 선물을 받으면 안 된다"와 "1번의 선물을 받으면 안 된다"는 제약은 동등한 제약 조건이다.