BOJ)2877 4와 7

문제:icpc.me/2877

4와 7로만 이루어진 수 중에서 K번째로 작은 수를 출력하는 문제이다.

각 숫자가 4와 7로만 이루어졌기 때문에 우리는 N의 자리 수는 2^N개 밖에 존재하지 않는다는걸 알 수 있다.

이를 이용하여 K번째로 작은 수가 L자리수라는 걸 알 수 있다.

이후 L자리에서 V번째로 작은 수는 결국 이진수로 생각하면 비트가 1인 수는 '7' 비트가 0인 수는 '4'가 된다.  

따라서 V의 각 비트를 조사하여 답을 출력해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int k, a[31], l;
int main() {
    for (int i = 0; i < 31; i++)
        a[i] = (1 << i);
    scanf("%d", &k);
    for (int i = 1; i < 31; i++) {
        if (k > a[i])
            k -= a[i];
        else {
            l = i;
            break;
        }
    }
    k--;
    for (int i = l - 1; i >= 0; i--) {
        if (k&a[i])
            printf("7");
        else
            printf("4");
    }
    return 0;
}