2^1, 2^2 ··· 2^N의 추들 이 있고 이 추들을 저울에 놓을 때
왼쪽이 오른쪽보다 무게가 무거워지지 않게 추를 놓는 경우의 수를 구하는 문제입니다.
개인적으로 어려웠던 문제입니다… ㅠ
딱 봐도 수학 문제 같은데 계속 풀리지 않아 힘들었습니다…
마치 작성일에 한 코포 C 번… C 번…
추의 무게가 모두 2n 꼴이기 때문에 순서대로 놓는다 가정했을 때 i 번째 추를 놓을 때
1 ~ i - 1번 추를 모두 오른쪽에 놨다고 해도 i 번째 추가 더 무겁기 때문에 오른쪽에 놓아야 합니다.
\(2^1 + 2^2 + 2^3 + \ldots + 2^{i-1}\) < \(2^i\)
그래서 놓으려는 추보다 놓은 추들 이 가벼울 때는 무조건 오른쪽에 놔야 합니다.
그렇다면 i-1개의 추를 저울에 놓는 경우의 수를 F[i-1]라고 하겠습니다.
i 번째 추를 마지막 순서에 놓는 경우의 수는 F[i-1]입니다. 다른 추들 이 다 가볍기 때문에 오른쪽에 놓을 수밖에 없죠.
조금 다르게 이번엔 1번째 추를 마지막에 두겠습니다.
2~i 번째 추가 배열되어 있는 거죠. 그래도 2~i 번째 추를 놓는 경우의 수와 1~i-1 번째 추를 놓는 경우의 수는 같습니다.
1, 2, 3, 4 대신 2, 3, 4, 5를 놓는 경우의 수는
1 -> 2, 2 -> 3, 3 ->4, 4 -> 5로 하나씩 미뤄서 생각하시면 결국 상대적으로 무게의 크기가 1,2,3,4와 같기 때문에
경우의 수가 똑같습니다.
대신 1번 추를 마지막에 놓을 때는 왼쪽, 오른쪽 둘 다 놓을 수 있습니다.
그다음 2번 추를 마지막에 놓을 겁니다.
1번 추 경우와 같이 1,2,3,4 대신 1,3,4,5를 놓는다면
2->3, 3->4, 4->5로 하나씩 미뤄서 생각하시면 1,2,3,4와 같은 경우의 수를 얻을 수 있습니다.
이렇게 1~i-1 번까지 마지막에 놓는 경우의 수는
2 * (i - 1) * F[i-1]입니다.
그렇다면 F[i]은
F[i] = i 번째 추를 마지막에 놓을 때 + 1~i-1 번째 추를 마지막에 놓을 때
= F[i-1] + 2 * (i-1) * F[i-1]
F[i] = (2*i - 1) * F[i-1]
위와 같이 구하실 때 int형 범위가 넘어갈 수 있으니 long long으로 연산하시면 됩니다.
수학 문제들 참 어렵네요… ㅠ
코드포스를 위해서라도 수학 문제를 많이 풀어봐야겠습니다..!
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define mod ((int)1e9+9)
using namespace std;
int main() {
FIO;
int n, f = 1; cin >> n;
FOR(i,1,n) f = (1ll * f * (2*i - 1)) % mod;
cout << f << '\n';
return 0;
}