boj, 백준) 1947. 선물 전달 ( C / C++ )

1. 문제 링크

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

1947번: 선물 전달

2. 문제 설명

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

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

 

3. 문제 힌트

기존의 그룹(n - 1명)에 최적화된 답을 알고 있다고 가정하자.

 

n - 1명이 있는데, 새로운 사람x가 들어온다. ( 이제 n명이 됨. dp[n]을 구할 것. )

(1) x가 1번사람이 받은 선물과 바꾼다. (1번 사람의 선물이 아닌, 1번 사람이 받은 선물이다.)

(2) x가 1번 사람의 선물과 바꾼다. ( 1번 사람의 선물과 바꿈.)

 

이점을 고려해서 다시 풀어보자.

 

 

4. 문제 풀이

풀고나서 다른 분들의 풀이를 보니 '완전 순열'이라고 하더라. 알아두면 좋을 것 같다.

 

문제 힌트에서 나왔던 (1),(2)에 대해서 살펴보자.

 

(1) x가 1번사람이 받은 선물과 바꾼다. (1번 사람의 선물이 아닌, 1번 사람이 받은 선물이다.)

 

그러면 1번 사람과 x사람이 선물을 맞교환했을 때 생길 수 있는 경우의 수는 dp[n-1]이다.

1번 사람~n-1번 사람까지 다 바꿔 볼 수 있으니 

첫 번째 경우의 수 : (n-1)*dp[n-1]

 

(2) x가 1번 사람의 선물과 바꾼다. ( 1번사람의 선물과 바꿈.)

 

1번 사람은 1번 선물을 갖고 있을 것이고, 2~n-1번 까지는 자기 것이 아닌 상대방의 것을 가지고 있다고 생각할 수 있다.

따라서 자기 자신을 제외한 dp[n-2]만큼 있고, 1~n-1번 사람까지 적용 가능하다

두 번째 경우의 수 (n-1)*dp[n-2]

 

즉 dp[n] = (n-1)(dp[n-1] + dp[n-2])라고 할 수 있다.

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
long long int dp[1000001];

int main()
{
	scanf("%d", &n);
	dp[2] = 1;
	dp[3] = 2;

	for (int i = 4; i <= n; ++i)
		dp[i] = ((dp[i - 1] + dp[i - 2])*(i - 1)) % 1000000000;

	printf("%lld", dp[n]);
	return 0;
}

6. 결과 사진