[ 백준 2248 ] 이진수 찾기

문제

이진수 찾기 2248번

스스로 풀지 못해 다른 블로그의 풀이를 보고도 이해가 쉽게 되지 않아서 여러 번 봤었던 문제이다. 내 방식대로 이해해보려고 노력해보았다.

풀이

I번째로 오는 이진수를 찾기 위해서, N개의 각 자리에서 1, 0인지를 알아내야 한다.

이를 위해 DP를 이용해 길이가 n이고 사용된 개수가 l이하인 이진수의 개수를 구한다.

cache[n][l] = cache[n-1][l-1] + cache[n-1][l]

길이가 N이고 사용한 1의 개수가 l개일때 i번째 이진수를 찾아내기 위해서는 i와 cache[n-1][l](pivot)을 비교해야 한다.

• pivot >= i 인 경우: 나머지 n-1개의 자리수에서도 i번째로 큰 수가 충분히 나올 수 있다는 것을 의미한다. 이 경우에는 현재 자리수를 0으로 만들고, 나머지 자리수에서 i번째로 큰 수를 찾을 수 있을 것이다. (굳이 현재 자리수를 포함하지 않더라도, 나머지 n-1개 자리수끼리도 i번째 수를 만들 수 있다.)

• pivot < i 인 경우: 나머지 n-1개의 자리수에서 l개의 1을 가지고 이진수를 만들었는데도 i개의 수가 나오지 않았으므로, 현재 자리수를 포함하여 1로 만들어야 한다. (나머지 n-1개 자리수끼리는 i번째로 큰 수를 만들 수 없다.)
  그 후, 나머지 n-1개의 자리수에서는 l-1개의 1을 가지고 i-pivot번째의 수를 찾아면 된다.

N의 범위가 [1, 31]이므로 long long 형을 써야한다.

코드

풀이 출처 DICE님 블로그

#include <iostream>
#include <string.h>
typedef long long ll;
using namespace std;

int N, L;
string ans = "";
ll I, cache[35][35];

// 길이가 n이고 사용된 1의 개수가 l 이하인 이진수의 개수 
ll getBinaryCount(int n, int l) {
	ll& ret = cache[n][l];

	if (ret != -1) return ret;
	if (n == 0 || l == 0) return ret = 1;

	// 1인 비트를 사용하지 않고 넘어가기 
	ret = getBinaryCount(n - 1, l);
	// 1인 비트가 남아있는 경우, 비트 사용
	if (l > 0) ret += getBinaryCount(n - 1, l - 1);

	return ret;
}

// 길이가 n이고 사용한 1인 비트의 개수가 l개일 때 i번째 이진수 찾아내기 
void findIthNumber(int n, int l, ll i) {
	if (n == 0) return;
	
	// n은 남아있지만 사용 가능한 비트가 없는 경우, 나머지는 0으로 채우기 
	if (l == 0) {
		for (int i = 0; i < n; i++) {
			ans += '0';
		}
		return;
	}

	ll pivot = getBinaryCount(n - 1, l);
	
	// 나머지 n-1개의 자리수에서도 i번째로 큰 수가 충분히 나올 수 있다.
	if (pivot >= i) {
		ans += '0';
		findIthNumber(n - 1, l, i);
	}

	// 나머지 n-1개 자리수끼리는 i번째로 큰 수를 만들 수 없다.
	else {
		ans += '1';
		findIthNumber(n - 1, l - 1, i - pivot);
	}
}

int main() {
	cin >> N >> L >> I;

	memset(cache, -1, sizeof(cache));

	findIthNumber(N, L, I);
	cout << ans << endl;

	return 0;
}