[백준] 1947번: 선물 전달

문제

[백준] 1947번: 선물 전달

분석

사람 수 N이 주어질 때 모든 사람이 선물을 하나씩 받으며, 자기 자신한테 주는 경우는 없다고 할 때, 선물을 나누는 경우의 수를 구하는 문제이다.

어떤 사람 i가 선물을 나눠줄 수 있는 선택지는 자기 자신을 뺀 i-1개이다.
이때 선물을 받은 j의 상황은 두 가지로 나뉜다.
1. i랑 맞교환 하고 나머지 i-2명 끼리 알아서 선물 나눈다.
2. i랑 맞교환 하지 않는 경우(이미 j는 i의 선물을 받았음), i를 포함한 n-1명이 선물을 나눠가지는데, i는 j한테 받지 않아야 하므로, 각자 못받는 경우 1개를 가지고 선물을 나누는 상황과 같아진다.

위의 설명을 코드 점화식으로 바꾸면
dp[i] = (i-1) * (dp[i-2]+dp[i-1]) 이다.
여기서 주의할 점은 곱하는 순간 이미 int의 범위가 넘어간다. 따라서 dp는 long으로 설정해주고,
미리 상수로 정해둔 MOD = 1,000,000,000로 나머지 연산을 한다.

반복문이 N 만큼 진행하기 때문에 O(N)이 시간 복잡도이다.

코드

해결언어 : Java

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

public class Main {
	static final int MOD = 1_000_000_000;
	static int N;
	static long[] dp;

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

}