[백준]선물 전달

/* 문제설명 */

이번 ACM-ICPC 대회에 참가한 모든 사람들은 선물을 하나씩 준비했다.

대회가 끝나고 난 후에 각자 선물을 전달하려고 할 때, 선물을 나누는 경우의 수를 구하는 프로그램을 작성하시오.

모든 사람은 선물은 하나씩 받으며, 자기의 선물을 자기가 받는 경우는 없다.

입력

첫째 줄에 ACM-ICPC 대회에 참가한 학생의 수 N(1≤N≤1,000,000)이 주어진다.

출력

경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다.

 

 

 

 

---

 

 

 

/* 풀이방법 */

 

 

완전순열

---

 

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class b1947 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] M = new int[1000001];
		int answer = 0;
		if(N==1) {
			answer=0;
		}else if(N==2) {
			answer=1;
		}else {
			M[1] = 0;
			M[2] = 1;
			for(int i =3;i<=N;i++) {
				long temp = ((long)(i-1) * ((M[i-1] + M[i-2])))%1000000000;
				M[i] = (int)temp;
			}
			answer = M[N];
		}
		
		
		System.out.println(answer);
	}
}