algospot - morse

//algospot - morse
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 1000000000
 
int N, M, K;
string s;
 
void init()
{
    cin >> N >> M >> K;
    s.clear();
}
 
int C(int u, int v)
{
    v = u-v > v ? v : u-v;
    long long t = 1;
    for (int i = 0; i < v; ++i)
    {
        t = t *(u-i)/(i+1);
        if (t > INF)
            return INF + 1;
    }
    return t;
}
 
void dp(int n, int m, int k)
{
    if(n == 0)
    {
        for(int i = 0; i<m; ++i)
            s += 'o';
        return;
    }
    else if(m == 0)
    {
        for(int i = 0; i<n; ++i)
            s+= '-';
        return;
    }
    int sum = n + m - 1;
    int temp = C(sum, n - 1);
    if (temp < k)
    {
        s += 'o';
        dp(n, m - 1, k - temp);
    }
    else
    {
        s += '-';
        dp(n - 1, m, k);
    }
}
 
int main()
{
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        dp(N, M, K);
        cout << s << "\n";
    }
}

 

 

 

 

 

 

https://algospot.com/judge/problem/read/MORSE

algospot.com :: MORSE

 

 

 

 

 

 

MORSE

k번째 답 계산하기

이항계수는 분자는 내림차순, 분모는 오름차순으로 그때그때 곱하고 나누어주면 나머지가 없는 성질을 이용해 그때그때 구했습니다.