백준 2248 - 이진수 찾기

icpc.me/2248

 

Step 1.

n자리의 이진수에서 비트 r개를 쓰는 경우의 수는 $\binom{n}{r}$이 된다.

 

이항 계수를 구현하고 누적합을 통해 n자리에서 r개 비트 이하를 쓰는 경우의 수도 구해주자.

 

0으로 시작하는 이진수도 인정됨에 유의한다. 즉 0이 첫번째 이진수가 되겠다.

 

n자리까지 n을 초과한 비트의 갯수만큼 사용하는 경우의 수는 n개의 비트를 사용한 것으로 간주하여 누적합에 반영해주자.

Step 2.

이항 계수의 누적합을 구하면 n부터 1까지 반복문을 돌려주자.

 

$idx$번째 자리와 $l$개의 비트가 남아있을 때

 

이항 계수의 누적합 := prefixsum[idx][l]

남은 자릿수 := i라고 하자.

 

prefixsum[idx - 1][l] < i 이면 $idx - 1$번째까지 비트 $l$개를 쓴 경우보다 뒤에 있는 수가 되므로 $idx$번째는 1로 채울 수 있다. 1을 출력해주자. 비트를 한 개 사용한 것이므로 $l$도 하나 빼주는 것을 잊지 말자

 

비트를 모두 소진하거나 위 조건을 만족하지 않을 때 0을 출력하면 정답이 된다.

 

전체 코드

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <numeric>
 
using namespace std;
using ll = long long;
 
int n, l;
ll ith;
ll dp[32][32];
ll prefixbino[32][32];
 
ll bino(int n, int r)
{
    if (n < r || n < 0 || r < 0)
        return 0;
    
    ll &ret = dp[n][r];
 
    if (ret != -1)
        return ret;
    
    return ret = bino(n - 1, r) + bino(n - 1, r - 1);
}
 
int main()
{
    memset(dp, -1, sizeof dp);
    dp[0][0] = dp[1][0] = dp[1][1] = 1;
 
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> l >> ith;
 
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= 31; ++j)
           for (int k = 0; k <= j; ++k)
                prefixbino[i][j] += bino(i, k);
    
    for (int i = n; i >= 1; --i)
    {
        if (!l)
        {
            cout << 0;
            continue;
        }
            
        if (prefixbino[i - 1][l] < ith)
        {
            cout << 1;
            ith -= prefixbino[i - 1][l--];
        }
        else
            cout << 0;
    }
}