[1947] 선물 전달

✔ 선물 전달

[백준 1947]

문제 분석하기

N개의 원소의 집합에서 원소들을 재배열할 때 이전과 같은 위치에 배치되는 원소가 1개도 없게 하는 완전 순열 문제

손으로 풀어보기

1. N명일 때 선물을 교환할 수 있는 모든 경우의 수 배열 D[N] 배열을 선언
2. D 배열을 초기화
   • 한 명일 때 다른 사람에게 선물할 수 없으므로 D[1] = 0
   • 두 명일 때 서로 교환만 가능하므로 D[2] = 1
3. 완전 순열 점화식으로 정답을 구함
   • 선물을 교환하는 방식으로는 양방향 교환과 단방향 교환이 존재하며
     양방향 교환 시 남은 경우의 수는 D[N - 2], 단방향 교환 시 남은 경우의 수는 D[N - 1]이며
     자기 자신이 아닌 학생에게 선물할 수 있으므로 N - 1명에게 선물을 전달할 수 있음
   • D[N] = (N - 1) * (D[N - 2] + D[N - 1])

슈도코드 작성하기

D(N명일 때 선물을 교환할 수 있는 모든 경우의 수 배열)
D[1] = 0
D[2] = 1
for(i -> 3 ~ N) {
    i명이 교환할 수 있는 모든 경우의 수 = (i - 1) * (D[i - 1] + D[i - 2]) % mod
}
D[N]값 출력하기

코드 구현하기

/**
 * 1947) 선물_전달
 */
public class D083_1947 {
    static int N;
    static long mod = 1000000000;
    // D(N명일 때 선물을 교환할 수 있는 모든 경우의 수 배열)
    static long D[] = new long[1000001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(학생의 수)
        N = sc.nextInt();
        D[1] = 0;
        D[2] = 1;
        // i명이 교환할 수 있는 모든 경우의 수
        for (int i = 3; i <= N; i++) {
            D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % mod;
        }
        // D[N]값 출력하기
        System.out.println(D[N]);
    }
}