2248. 이진수 찾기

2248번: 이진수 찾기

---

$N$자리의 이진수 중에서 1인 비트가 $L$개 이하인 이진수를 오름차순으로 정렬했을 때, $I$번쨰 이진수를 구하는 문제이다. 이진수는 0으로 시작할 수 있음에 주의하자.

 

이진수를 결정하려면 이진수의 각 자리가 0인지 1인지 결정해야 한다. 현재 자리가 0과 1 중 무엇인지 결정하려면, 현재 자리를 0(또는 1)로 결정했을 때 몇 개의 이진수를 만들 수 있는지 알아야 한다. 

 

문제를 쉽게 만들기 위해, $N$자리의 이진수를 만드는 데 1을 정확히 $L$개 사용한다고 가정하자. 만약 현재 자리를 0으로 결정했다면,하위 $N-1$ 비트에 1을 $L$개 사용할 수 있다. 따라서 매개변수를 $N-1,~L$로 두고 같은 계산을 수행하면 구하는 값을 얻을 수 있다. 어?

 

반대로 현재 자리를 1로 결정했다면, 하위 $N-1$ 비트에 1을 $L-1$개 사용할 수 있다. 따라서 매개변수를 $N-1, ~L-1$로 두고 같은 계산을 수행하면 구하는 값을 얻을 수 있다. 이제 알겠지? 현재 자리에 0을 놓는 경우의 수와 1을 놓는 경우의 수를 합하면 된다.

 

그런데 같은 연산이 매개변수만 달리하여 반복되므로 다이나믹 프로그래밍을 적용할 수 있다. 구체적으로 1을 $L$개 사용하여 $N$자리의 이진수를 만드는 경우의 수를 $dp(n,~l)$이라 할 때, $dp(n,~l) = dp(n-1,~l) + dp(n-1,~l-1)$이다. 

 

원래 문제에서는 1을 $L$개 이하로 사용할 수 있으므로, $N$자리의 이진수 중 1을 $L$개 이하로 사용하여 만들 수 있는 이진수의 개수 $sum(n,~l) = \sum_{i=0}^{k}{dp(n,~i)}$로 정의할 수 있다.

 

이제 이진수를 구해 보자. 현재 자리에 0을 놓았을 때 만들 수 있는 이진수의 개수는 $sum(n-1,~l) = k$개이다. 만약 $I <= k$라면 현재 자리에 0을 놓아야 하고, 그렇지 않다면 1을 놓아야 한다. 높은 자릿수부터 시작해서 이 계산을 반복하면 된다.

맞왜틀 1

$dp$를 계산할 때 terminal case에 주의하자. $n=1$이면 $dp(n,~l) = (l == 0)$이고, $l=0$이면 $dp(n,~l)=1$이다.

맞왜틀 2

$I$는 최대 $2^{31}+1$까지 주어질 수 있다. 따라서 32비트 부호 있는 정수형으로는 입력을 정확히 받을 수 없다. 더 큰 정수형을 사용하거나, 정수 범위에 제한이 없는 언어를 사용해야 한다.

맞왜틀 3

정답을 구할 때, 현재 자리에 1을 놓았다면 $I$에서 $k$를 빼고, $l$을 1 감소시켜야 한다. 0을 놓았다면 아무것도 하지 않아야 한다.

---

은근히 까다로웠던 문제.