https://www.acmicpc.net/problem/1947
1947번: 선물 전달
경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다.
www.acmicpc.net
DP 문제 ( 수열의 유도 및 구현 )
개념을 알고 모르고의 유무로 난이도가 극명하게 갈린다고 할 수 있는 문제.
이 문제에서 요구하는 수열은 "교란순열" 혹은 "완전순열" 이다.
44라는 숫자가 나오면 한번쯤 의심해볼만할듯.
dp[i] = (dp[i-1]+dp[i-2])*(i-1)
교란순열을 구하는 DP 점화식은 다음과 같다.
DP[i] : i명끼리 조건에 맞게 선물을 분배하는 경우의 수
유도
각각의 사람의 번호를 $a_i$ , 선물의 번호를 $b_i$ 로 둔다.
어떠한 사람 A가 선물을 하는 경우는 $(N-1)$ 가지이다.
이 각각의 상황에 대해서, 선물을 받은 사람을 A' 이라고 하면
1. A와 A' 이 서로 선물을 주고받음.
이 경우에는 A와 A' 두사람을 제외한 N-2명의 사람에 대해서
또 사람 A를 뽑고 선물을 분배하는 과정을 반복하면 된다.
이러한 과정의 반복은 DP의 정의에 의해 DP[N-2] 와 같다.
2. A'는 A에게 선물을 주지 않고 다른 사람에게 줌.
이 경우에는 A를 제외한 N-1명끼리 선물을 분배한 후
남은 단 한개의 선물을 A에게 주면 된다.
이 과정은 DP의 정의에 의해 DP[N-1] 이다.
1번과 2번 과정이 동시에 일어날 수 없으므로,
DP[N] 을 만드는 전체 경우의 수는 (N-1) * (DP[N-1] + DP[N-2]) 이다.
수 범위가 커질 수 있으므로 long long 형으로 선언해줄것
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[1234567] = {0};
int main(){
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
for(int i=3; i<=1000000; i++){
dp[i] = (dp[i-1]+dp[i-2])*(i-1) % 1000000000LL;
}
int N;
cin >> N;
cout << dp[N];
return 0;
}
반응형