백준 2248 이진수 찾기

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 이전에 쓴 1256 사전과 유사한 문제입니다. N자리의 이진수가 있을 때 L개 이하의 1이 존재가능 하다고 할 때 이중에서 I번째 순서의 이진수를 찾는 문제입니다. I는 범위안에 있도록 주어진다 했으니 최대 가능한 I가 2^31번째 일것입니다. 따라서 이전의 사전 문제처럼 dp를 이용하여 개수들을 저장하고 skip하는 방식으로 해결을 하여야 합니다.

 

dp배열에는 이항계수 성질인 nCk = n-1Ck-1 + n-1Ck 를 이용하여 n개의 비트중 1이 k개일때를 저장 했습니다.

dp[n][k] = dp[n-1][k-1] + dp[n-1][k] 

이렇게 저장 한뒤 원하는 이진수를 찾는 함수를 만들어 주어야 합니다.

findfunc(int N, int L ,long long I) 라고 함수를 만들었습니다. 각 매개변수의 의미는 N개의 비트중 1이 L개 까지 사용 가능하고 I번째 순서를 찾아야 한다 입니다. I를 int로 두면 2^31 때문에 틀리게 됩니다.(이것때문에 몇번 틀렸습니다 ㅠㅠ)

 

skip이라는 변수를 하나 두고 

dp[N-1][0] + ~ dp[N-1][L] 까지의 합을 저장해 줍니다. (N-1개의 비트중 L개 이하의 1이 들어가는 이진수의 개수)

그런뒤 이 skip이 I보다 크거나 같으면 0을 붙여주고 그렇지 않다면 1을 붙여주면 됩니다.

 

아래는 코드입니다.

 

 #include <iostream>
#include <string>

using namespace std;

long long dp[33][33]; //nCk
string ans;

void findfunc(int N, int L, long long I) { // L은 채울수있는 1의개수 I는 남은 순서 수

    if(N == 0) return;
    if(L == 0) {
        for(int i = 0; i < N; i++)
            ans += '0';
        return;
    }

    long long skip = 0;
    for(int i = 0; i <= L; i++)
        skip += dp[N-1][i];

    if(skip >= I) {
        ans += '0';
        findfunc(N-1, L, I);
    }
    else {
        ans += '1';
        findfunc(N-1, L-1, I-skip);
    }

    return;
}


int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N,L;
    long long I;
    cin >> N >> L >> I;

    dp[0][0] = 1;
    for(int i = 1; i < 33; i++) {
        dp[i][0] = 1;
        dp[i][i] = 1;
    }

    for(int i = 2; i <= N; i++) {
        for(int j = 1; j <= i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }

        findfunc(N,L,I);
        cout<<ans<<'\n';

    return 0;
}