[BOJ 2248 // C++] 이진수 찾기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2248번 문제인 이진수 찾기이다.
문제는 아래 링크를 확인하자.

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

2248번: 이진수 찾기

큰 자리부터 채워나가며 매 순간 다음 자리로 1을 쓸지 0을 쓸지를 결정해나가는 식으로 문제를 해결하자.

 

이번 차례에 0을 써야 할 필요충분조건은 이번 자리에 0을 채워넣어도 앞으로 작성할 수 있는 문자열의 개수가 K개 이상 남아있어야 하는 것이다. 또한, 이번 차례에 1을 쓰게 된다면 K의 값에서 "이번 자리에 0을 채워넣어 앞으로 작성할 수 있는 문자열의 개수"를 빼주자.

 

위의 계산에 필요한 "남은 작성할 수 있는 문자열의 개수"는 남은 자리들 중 1을 (남은 개수만큼) 채워넣을 경우의 수, 즉 조합(combination)값을 이용해 계산할 수 있다. 이는 파스칼의 삼각형을 미리 계산해두는 것으로 쉽게 이용할 수 있다.

 

아래는 제출한 소스코드이다.

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

ll comb[32][32];

void init() {
	for (int n = 0; n < 32; n++) {
		comb[n][0] = comb[n][n] = 1;
		for (int r = 1; r < n; r++) {
			comb[n][r] = comb[n - 1][r - 1] + comb[n - 1][r];
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	init();

	ll N, L, K; cin >> N >> L >> K;
	while (N) {
		ll cnt = 0;
		for (int i = 0; i <= L; i++) cnt += comb[N - 1][i];
		if (cnt >= K) cout << 0;
		else cout << 1, L--, K -= cnt;
		
		N--;
	}
}