백준 2248: 이진수 찾기

문제 요약

N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수는 0으로 시작할 수도 있다.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

일반적인 DP 문제지만, 조금 어렵다.

우선 문제를 분해해보자. N자리이고, 1이 M개 이하인 문자열의 개수는 DP로 풀 수 있다. 그것이 풀이 코드의 sol()에 구현되어 있다.

n자리이고, m개 이하의 1을 갖는 이진수, 이에 대한 점화식은 dp[n][m] = sol(n - 1, m) + sol(n - 1, m - 1);이 된다. 첫 번째 자리가 0일 경우와 1일 경우로 나누어, 두 경우를 합한 것이다.

이제 그 정보를 활용하여 I(=k)번째 크기의 이진수를 구해보자. 앞의 점화식에서 두 경우로 나눈 것을 기억해보자. 현재 자리의 수가 0인지 1인지 파악하기 위해서는 위의 정보가 필요하다. 즉, k번째의 이진수가 0~인지, 1~인지 파악해야 한다. k가 sol(n - 1, m)보다 작거나 같다면 현재 자리의 수는 0이 될 것이다. (k는 1부터 센다고 가정) 아니라면 현재 자리의 수는 1이다. 그러고 이런 식으로 다음 자리의 수를 계산해나간다. 이 과정이 build()에 구현되어 있다.

DP에서 끝나지 않고 수를 조립해나가는 문제였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int dp[32][32], N, L;
long long int I;
char res[32];

int sol(int n, int m) {
	if (dp[n][m] != -1) return dp[n][m];
	if (n == 0 || m == 0) return dp[n][m] = 1;

	dp[n][m] = sol(n - 1, m) + sol(n - 1, m - 1);

	return dp[n][m];
}

void build(int n, int m, long long int k, int idx)
{
	if (n == 0) {
		res[idx] = '\0';
		return;
	}
	if (m == 0) {
		int i;
		for (i = 0; i < n; i++)
			res[idx + i] = '0';
		res[idx + i] = '\0';
		return;
	}
	int pivot = sol(n - 1, m);
	if (k <= pivot) {
		res[idx] = '0';
		build(n - 1, m, k, idx + 1);
	}
	else {
		res[idx] = '1';
		build(n - 1, m - 1, k - pivot, idx + 1);
	}
}

int main()
{
	memset(dp, -1, sizeof(dp));
	cin >> N >> L >> I;
    
	build(N, L, I, 0);

	cout << res;
	return 0;
}