[BOJ] 14556 - Balance

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

BOJ - Balance

문제 유형: 수학, 조합론

문제 난이도: Gold II

시간 제한: 1초

메모리 제한: 256MB

 

문제

리유나는 양팔저울을 가지고 놀고 있다. 무게가 2^1, 2^2, ⋯, 2^N인 N개의 추가 있고, 적당한 순서로 서로 다른 N개의 추를 하나씩 놓는 동안, 왼쪽의 무게가 오른쪽의 무게를 넘지 않도록 하고 싶다. 추를 놓는 순서의 경우의 수를 구하여라.

 

입력

첫째 줄에는, N이 주어진다. (1≤N≤50000)

 

출력

첫째 줄에, 추를 놓는 순서의 경우의 수를 구하여라. 단, 답이 매우 클 수 있으니, 1000000009 (=10^9+9) 로 나눈 나머지를 구하여라.

 

풀이

f(n)를 n개의 추를 놓기 위한 방법의 수라 하자.

2^N짜리 추는 반드시 맨 오른쪽에 놓여야 한다.

 

n번째가 맨 마지막에 놓이는 경우는 f(n-1)가지,

2^n이 아닌 다른 수 2^i가 맨 뒤에 놓이는 경우는 2(n-1) * f(n-1)가지이다. 이들은 양쪽 중 하나에 갈 수 있는데, 어차피 2^n은 오른쪽에만 있어야 한다.

점화식은 f(n) = (2n-1) * f(n-1), f(1) = 1이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = 1e9 + 9;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    ll ans = 1;
    for (int i = 1; i < 2 * n; i += 2) {
        ans *= i;
        ans %= MOD;
    }

    cout << ans << "\n";

    return 0;
}