백준 1146 - 지그재그 서기

지그재그 순열로 배치하는 경우의 수를 구하는 문제이다.

 

모듈러 연산에 유의하면서 경우의 수를 구하는 점화식을 구현하자.

 

전체 코드

#include <bits/stdc++.h>
 
#define mod 1000000
 
using namespace std;
using ll = long long;
 
int n;
int euler[101][101];
 
int zigzag(int n, int k);
 
int main()
{
    memset(euler, -1, sizeof euler);
    euler[0][0] = 1;
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n;
 
    if (n == 1)
    {
        cout << 1;
        return 0;
    }
 
    cout << zigzag(n, n) * 2 % mod;
}
 
 
int zigzag(int n, int k)
{
    if (!k)
    {
        if (!n)
            return 1;
        else
            return 0;
    }
    
    int &ret = euler[n][k];
 
    if (ret != -1)
        return ret;
    
    return ret = (zigzag(n, k - 1) + zigzag(n - 1, n - k)) % mod;
}