티스토리 뷰

알고리즘 관련/BOJ

BOJ)2877 4와 7

JASON 자손9319 2017. 1. 15. 02:40

문제:icpc.me/2877


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <algorithm>
using namespace std;
int k, a[31], l;
int main() {
    for (int i = 0; i < 31; i++)
        a[i] = (<< 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)8983 사냥꾼  (0) 2017.01.15
BOJ)10277 JuQueen  (0) 2017.01.15
BOJ)2877 4와 7  (0) 2017.01.15
BOJ)2775 부녀회장이 될테야  (0) 2017.01.15
BOJ)5480 전함  (0) 2017.01.14
BOJ)10167 금광  (0) 2017.01.14
댓글
댓글쓰기 폼