[Algorithm]Baekjoon 1947번 :: 선물 전달

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

 

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int mod = 1000000000;
int n;
long long dp[1000001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n; 
 
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
 
    for (int i = 4; i <= n; ++i)
    {
        dp[i] = (dp[i - 1] + dp[i - 2] % mod) * (i - 1);
        dp[i] %= mod;
    }
 
    cout << dp[n];
}

 

 

몰랐는데 완전순열 문제의 형태라고 한다.

 

dp[n]을 n명의 사람이 자신의 것이 아닌 선물을 주고받는 값이라고 설정한다.

그럼 먼저 각각의 사람이 서로 주고받는 형태를 생각해보자.

예를들어 5명이있는데, 1번과 2번이 서로 주고받았다고 가정하면, 나머지 3명에 대한 dp값만 알면된다.

그리고 주고받는 상황은 i-1번이 발생하기 때문에 ( 1번과 2번, 2번과 3번,3번과 4번, 4번과 5번)

dp[i] += i-1 * dp[i-2]가 성립된다.

 

이 다음이 좀 헷갈릴 수 있다.

일단 먼저 우리는 dp[i]에 앞의 경우를 누적시켰다는것을 먼저 인지해야 한다.

즉, 서로 주고받는 형태에 대해선 이미 값을 누적시켰다.

그러니 새로 누적시키는 값에는 서로 주고받는형태는 당연히 없으며, 없어야 한다.

 

마찬가지로 5명이 있다고 가정한다.

먼저 3번이 1번한테 선물을 줬다.

그러면 현재 3번은 아무것도 들고있지 않고, 1번은 누군가한테 선물을 줘야하는 입장이다.

 

이 때! 1번이 누군가한테 선물을 줘야하는 입장이 아니라 3번이 누군가한테 선물을 줘야하는 입장이라고 생각해도 된다.

서로 주고받는경우에 대해선 이미 누적(계산)시켰으니 1번의 선물을 다시 3번한테 주면은 안된다.

그래서 이 선물은 3번을 제외한 누군가한테 뿌려야하는데, 이 때 이미 3번의 선물을 받은 1번은 일단 이 계산에서 제외시켜버리자.

그다음 현재상황을 따져보자.

 

사람은 2,3,4,5 (i-1명) 만큼이 있고,  3번은 자기고유의 선물을 들고있지 않으며(1번한테 줬으니까) 나머지는 다 자기고유의 선물을 들고있다. 여기서 끝이아니라 3번을 제외한 어딘가로 뿌려질 수 있는 1번의 선물도 있다는걸 잊으면 안된다.

 

여기서 임의로 뿌려질 수 있는 1번의 선물을 그냥 3번의 선물이라 생각해도 된다는 것이다. 

왜? 이 1번의 선물은 3번한테는 뿌려지면 안되고 그 외의사람들한테만 뿌려져야한다.

근데 3번의 선물또한(만약 있었다고 가정하면) 3번 자신한테는 뿌려지면 안되고 그 외의 사람들한테만 뿌려져야 한다.

 

그렇기 때문에 3번의 선물이라고 생각해도 된다는 것이다.

 

그러면 결국 그냥 dp[i-1]의 값이되는 것이다. 5명중에서 맨처음에 3번의 선물을 받은 1번을 계산에서 제외한, 나머지 4명에 대해서 서로 주고받는 경우이기 때문이다.

그리고 이 경우는 i-1번 발생한다.

그러면 dp[i] += i-1 * dp[i-1];

 

그러면 최종식은 dp[i] = i-1 * dp[i-2] + i-1 * dp[i-1] 이니까

dp[i] = (i-1) * (dp[i-2] + dp[i-1]이 된다.