선물 전달
Problem link: https://www.acmicpc.net/problem/1947
완전순열(교란 순열이라고도 불리는...) 문제이다.
결론부터 이야기하면 N개 원소에 대한 완전순열의 수 점화식은 아래와 같다.
CACHE[N]
=(N - 1) * (CACHE[N-1] + CACHE[N - 2])
점화식 유도는 아래와 같다.
수열이 아래와 같이 주어졌다고 해보자.
{1, 2, 3, ... N-2, N-1, N}
편의상 1번 원소
를 기준으로 점화식을 유도해보자(자명하게 다른 원소를 기준으로 유도해도 일반성을 잃지 않는다)
전체 경우의 수는 Case 1, Case 2의 합이 된다.
- Case 1)
1번 원소
와X번 원소
(X in [2, N]
)가 서로 선물을 맞바꾼 경우- 예시로 그리면 아래와 같은 경우가 될 것이다.
1번 원소
와X번 원소
의 선물 교환이 아래 테이블과 같이 고정되었으므로 Case 1)에 해당되는 경우의 수는 사실{2, 3, ..., X-1, X+1, ..., N-2, N-1, N}
수열의 완전순열 경우의 수와 같을 것이다.
(1번 원소
와X번 원소
를 빼놓은 수열임에 주의하자.)- 따라서,
X번 원소
를 고르는 경우의 수N-1
에CACHE[N-2]
를 곱하여(N-1)*CACHE[N-2]
을 얻는다.
1 | 2 | 3 | ... | X | ... | N-2 | N-1 | N |
---|---|---|---|---|---|---|---|---|
X | 1 |
- Case 2)
1번 원소
는X번 원소
(X in [2, N]
)에게 설물을 주었지만 X번 원소`는 다른 사람에게 선물을 준 경우- 이 경우는 아래 테이블의
{2, 3, ..., X, ... N-2, N-1, N}
열에{1, 2, 3, ..., X-1, X+1, ..., N-2, N-1, N}
을 채워 넣는 경우의 수를 구하면 된다. - 단, Case 1)을 별도로 고려해주었기 때문에
X번 원소
는1번 원소
에게 선물을 주면 안되므로 X열에는 1이 들어가면 안된다. - 잘 생각해보면 1이 그냥 X의 역할을 하는 N-1개 원소의 완전순열 경우의 수와 같음을 알 수 있다.
- 따라서,
X번 원소
를 고르는 경우의 수N-1
에CACHE[N-1]
를 곱하여(N-1)*CACHE[N-1]
을 얻는다.
- 이 경우는 아래 테이블의
1 | 2 | 3 | ... | X | ... | N-2 | N-1 | N |
---|---|---|---|---|---|---|---|---|
X |
#include <iostream>
#include <cstdint>
using namespace std;
uint64_t kMod = 1000000000;
uint64_t N;
uint64_t Solve(void)
{
if (N == 1)
{
return 0;
}
else if (N == 2)
{
return 1;
}
uint64_t pp = 0;
uint64_t p = 1;
uint64_t ans = 0;
for (uint64_t it = 3; it <= N; ++it)
{
ans = ((it - 1) * ((p + pp) % kMod)) % kMod;
pp = p;
p = ans;
}
return ans;
}
int main(void)
{
cin >> N;
cout << Solve() << '\n';
return 0;
}
Author And Source
이 문제에 관하여(선물 전달), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@aram_father/선물-전달저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)