백준 2877번 C++ 풀이

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

2877번: 4와 7

시간 제한	메모리 제한	solved.ac 티어
1 초	128 MB	골드 5

문제

창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 K(1 ≤ K ≤ 10^9)가 주어진다.

출력

첫째 줄에 창영이가 좋아하는 숫자 중 K번째 작은 수를 출력한다.

---

4와 7로만 이루어진 숫자중에서 k번째로 작은 숫자를 구하는 문제이다. 처음 봤을때는 DP일거 같긴 했지만, 마땅한 방법이 생각이 나지는 않아 생각을 금방 버렸다.

 

필자는 해당 문제를 수학적으로 접근했다. 4와 7로만 이루어진 숫자를 오름차순으로 정렬해보면, 

 

4, 7 / 44, 47, 74, 77 / 444, 447, 474, 477, 744, 747, 774, 777 / 4444 ....

 

길이별로 군을 지었을때, 해당 군의 개수는 2^n개만큼의 원소를 가진다. 증명할 필요도 없이 자명하다. 그러니 해당 군의 정보와, 그 군에서 몇번째 원소인지를 알아낸다면 쉽게 작성할 수 있을 것이다. 이를 알아내려면 등비수열의 합을 역으로 이용하면 된다. 그리고 문제를 분석하면서 알아냈는데, 해당 군의 정보를 작성해보면

 

 

이진수처럼 동작한다는 것을 알 수 있었다. 생각해보면 0을 4로, 1을 7로 생각해보면 동작 과정이 2진수와 유사하기 때문에 이 역시 당연한 것이었다. 다만 4와 7로 되어있었기 때문에 이를 눈치채기 조금 어려웠을 뿐인것이다.

 

k번째의 숫자는 등비수열의 합 + c가 되고, 즉 2(2^n - 1) + c의 형태로 나타낼 수 있다. 이때 n은 맨 처음 군을 0군이라고 할때의 n번째 군이다. k가 위치한 군은 n+1군일 것이다.이를 찾아내고, c를 통해 이진수로 변환하여 4와 7을 적당히 붙여주면 될 것이다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define ALL(X) (X).begin(), (X).end()
using namespace std;

void sol(int k) {
    // k = 2(2^n - 1) + c 로 분해
    int n = (int)log2((k - 1) / 2. + 1);
    int c = k - (int)pow(2, n) * 2 + 1;
    string answer = "";
    bitset<32> ans_bit = c;
    
    for (int i = 0; i <= n; i++) {
        if (ans_bit[i]) answer.append("7");
        else answer.append("4");
    }
    reverse(ALL(answer));
    cout << answer << endl;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);    
    int k; cin >> k;
    sol(k);
}