이진수 찾기

백준 2248번: 이진수 찾기

아이디어

dp[자릿수][1의 최대 개수]에 경우의 수를 기록.
nCr 계산해서 dp테이블 채운다고 생각하면 편하다.
이 때 I번째 수를 구하는 방법은 다음과 같다.

N = 5, L = 3, I = 19일 때 00000~11100중에 19번째 수를 찾으면 된다.
맨 앞자리부터 채워보자.
만약 맨 앞자리가 1인 경우는 맨 앞자리가 0인 경우인 (0)0000 ~ (0)1110보다 무조건 뒤에 온다. 따라서 앞에서부터 1을 채우기로 결정한 경우, prefix sum으로 0000~1110까지 몇개인지 찾고 그걸 I에서 빼주면 된다.
이 때 앞으로 1을 몇개까지 더 사용할 수 있는지 계속 기록해야한다.

코드

#include <bits/stdc++.h>

using namespace std;
#define int long long

int N, L, I;

int dp[32][32]; // max, cur
int sum[32][32];

void print_ans(int idx) {
    idx--;
    int one = L;
    for (int i = N-1; i >= 0; i--) {
        if (sum[i][min(one, i)] <= idx) {
            cout << 1;
            idx -= sum[i][min(one, i)];
            one--;
        }
        else cout << 0;
    }
    cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> L >> I;

    dp[1][0] = 1;
    dp[1][1] = 1;
    sum[0][0] = 1;
    sum[1][0] = 1;
    sum[1][1] = 2;

    for (int i = 2; i < N+1; i++) {
        sum[i][0] = sum[i-1][0];
        for (int j = 0; j < min(i+1, L+1); j++) {
            if (j>0) dp[i][j] += dp[i-1][j-1]; // 1
            dp[i][j] += dp[i-1][j]; // 0
            if (j>0) sum[i][j] = sum[i][j-1] + dp[i][j];
        }
    }

    print_ans(I);
    return 0;
}

여담

int 범위를 벗어나서 흑마법을 사용했다.

#define int long long
signed main()