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

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

1947번: 선물 전달

 

1명  -  0

2명  -  1

3명  -  2

4명  -  9

5명  -  44

이기에 (dp[i-1]+dp[i-2])*(i-1) 의 점화식이 성립된다!

 

해당 점화식과 1000000000으로 나눈 값을 출력하면 간단히 해결~! 

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

public class Main {

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

}