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

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

1947번: 선물 전달

n 명의 사람이 서로의 선물을 교환하는데, 자기의 선물을 자기 자신이 받으면 안된다.

 

이러한 상황은 완전 순열을 이해하고 있으면 쉽게 구할 수 있다.

 

https://namu.wiki/w/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4

완전순열 - 나무위키

차근 차근 점화식을 떠올려보자.

 

dp[n] 을 n 명의 사람이 있을 때, 모자를 교환할 수 있는 경우의 수라고 가정하자.

 

사람이  0명이거나 1 명인 경우에는 당연히 dp[n] = 0 이다.

 

사람이 2 명이라면 dp[n] = 1 이다. 서로가 서로의 모자를 받는 경우밖에 없다.

 

n 명이라고 생각했을 때, 그 중 2명(a,b)을 특정지어서 생각해보자.

 

a 는 b 에게 선물을 주었다고 가정하고,

 

b 가 선물을 전달할 수 있는 경우는 두 가지 밖에 없다.

 

1. b 도 a 에게 주는 경우 (이러면 양방향으로 교환함)

>> 그러면 n 명 중에서 2 명이 받는 선물은 확정된 것이다. 그러므로 dp[n-2]

 

2. b 는 a 가 아닌 다른 사람에게 주는 경우

>> 그러면 b 가 준 선물을 받을 사람은 확정되지 않았고, b 가 a 로부터 선물을 받는다는 것만 확정된다. dp[n-1]

 

(*) 다시 대전제로 돌아가서, n 명 중에 a 와 b 를 선택하는 상황을 생각해보자.

a 는 골랐다고 치면, b 는 n-1 명 중에 1명이 될 것이다. 즉 b 를 고르는 경우의 수는 n-1 이다.

 

종합하면 dp[n] = (n-1)*(dp[n-1]+dp[n-2]) 와 같은 점화식을 얻을 수 있고,

 

이를 채워넣으면 문제를 해결할 수 있다.

 

※ 나머지 연산을 수행할 때에는, 테이블에 값을 넣기 전에 수행해야 한다는 것을 조심하자. 오버플로우가 발생해버리면 값이 잘못 저장되니까!

 

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        Scanner sc = new Scanner(System.in);
        long mod = 1000000000;
        int n = sc.nextInt();
        long [] dp = new long[1000001];

        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;

        for(int i = 3; i <= n; i++){
            dp[i] = (i-1)*(dp[i-2]+dp[i-1])%mod;
        }
        System.out.println(dp[n]);
    }
}