BOJ 2248 이진수 찾기

 

문제 링크 : https://www.acmicpc.net/problem/2248

2248번: 이진수 찾기

 

숫자는 평범한 크기 순으로 다루지만, 자릿수 1 의 사용에 제약이 있다.

주어진 문제보다 더 쉬운 문제는 N 자리의 수 중에서 L 개 이하의 1 이 사용된 수 전체의 개수를 구하는 것일텐데,

이것을 구해주는 함수 recur(N, L) 라 하자.  recur 함수를 구할 수 있으면 전체 문제도 해결할 수 있다.

 

1. 분석

1의 사용 횟수에 제약이 있는 상황에서

(1) I 번째 수가 무엇인지

(2) 반대로 특정 수가 주어졌을 때, 몇 번째 수인지

를 결정해 주는 공식(closed form)을 찾을 수 있다면 좋겠지만,

그렇지 않다면 이진 탐색 외에는 떠오르는 것이 없다. 

 

이진 탐색? 문제의 예를 가지고 설명한다.  

 

5 자리의 수 중에서 3 개 이하의 1 을 사용하여 만들어진 수 중에서 크기 순으로 19 번째 수를 찾아야 한다.

첫 자리($2^4$ 자리) 가 0 일 때, 3 개 이하의 1 로 19 개 이상의 수를 만들 수 있으면 첫자리는 0 이어야 하고

아니면 첫 자리는 1 이어야 한다. 

 

즉, 각 자릿수에서 0, 1 에 따라 분기하는 이진 탐색을 한다는 뜻인데, 

이는 앞서 말한 recur 의 값을 바탕으로 이루어지게 된다.

 

2. 사족

어리석음을 반성하기 위해서 기록을 남겨둔다.

평범한 재귀함수로 해결가능하지만 입력 조건을 가벼이 보다가 몇 시간을 헤맸다.

 

재귀함수에 굳이 설명을 붙이면,

재귀함수 recur(n, x) 는  n 개의 칸을 최대 x 개의 1을 사용해서 채워넣을 수 있는 경우의 수를 의미한다.

 

n개의 칸중 첫 칸에 0을 넣으면 소모된 1이 없으니 recur(n-1, x) 개의 경우의 수가 발생하고

첫 칸에 1을 넣으면 1 이 하나 소모되니 남은 칸은 n-1이고 남은 1은 x-1 이므로 recur(n-1, x-1)

 

즉, 

$$ recur(n,x)=recur(n-1,x)+recur(n-1,x-1) $$

(x==0 인 경우는 base case로 제거된다.)

 

최대 31 자리의 이진수에 관한 문제라 모든 입력 변수를 int 로 받아도 문제 없으리라 생각했다.

그런데...

 

일단 통과된 코드를 보자.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int N, L, ans[32];
ll I, dp[32][32];

ll recur(int n, int l){
    if(n==0 || l==0) return 1;

    ll &ret=dp[n][l];
    if(ret!=-1) return ret;
           
    ret=recur(n-1,l);
    ret+=recur(n-1, l-1);
    
    return ret;
}

void solve(int n, int l, ll num){
    if(n==0 || l==0) {
        for(int i=0;i<N;i++) printf("%d",ans[i]);
        printf("\n");
        return;
    }
    
    ll cnt=recur(n-1,l);
    if(num<=cnt) {
        ans[N-n]=0;
        solve(n-1, l, num);
    } else {
        ans[N-n]=1;
        solve(n-1, l-1, num-cnt);
    }
}

int main(){
    memset(dp, -1, sizeof dp);
    scanf("%d%d%lld", &N,&L,&I);
    solve(N,L,I);
}

 

long long 으로 정의된 변수들을 int 로 바꾸면 문제가 발생한다.

 

생각지 못했던 입력은

N=31, L=31 , I=2,147,483,648 ( \(=2^{31}\) )

이었다. 이 경우에 I 의 값을 int로 받으면 당연히 문제가 발생한다.

 

 

흠, 하지만 생각해보니 잘못된 입력이 어떻게 저장되는지 깊이 생각해본 적이 없었는데 나름 공부가 됐다.