[백준 2248] 이진수 찾기

문제 링크 => 2248번: 이진수 찾기 (acmicpc.net)

2248번: 이진수 찾기

---

다이나믹 프로그래밍 문제이다.

 

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

 

2차원 배열 memo[x][y] 를 설정했을때 x는 자릿수를 결정하도록 하고 y는 해당 자릿수 x에서 비트 1를 사용한 횟수라고 한다.

 

이때 x는 N보다 작거나 같아야 하고 y는 L보다 작거나 같아야 한다는 것은 분명하다.

 

따라서 이를 재귀함수와 여러번 호출을 방지함에 있어서 메모지에이션을 이용해야 한다.

 

풀이 code

---

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009

using namespace std;

long long n, l, k;
long long memo[32][32];

long long dp(int i, int j) {
	if (j == l || i >= n) return 1;
	if (memo[i][j]) return memo[i][j];
	return memo[i][j] = dp(i + 1, j) + dp(i + 1, j + 1);
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> l >> k;
	for (int i = 1, j = 0; i <= n; i++) {
		if (dp(i, j) >= k) cout << 0;
		else {
			cout << 1;
			k -= dp(i, j);
			j++;
		}
	}

	return 0;
}