※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
얼핏 보면 문제가 굉장히 어려워 보입니다. 제한인 k가 최대 10억번이기 때문에, 숫자를 그냥 이리저리 붙여보았다가는 시간초과가 분명해 보이기 때문입니다.
이 문제는 먼저 규칙을 찾아야 합니다. 한번 k=1 일 때 부터 10일 때까지를 쭉 써볼까요?
4 7 44 47 74 77 444 447 474 477
이걸 자리수 기준으로 나눠보죠
4 7
44 47 74 77
444 447 474 477
이미 짐작하신 분도 있겠지만, 이것은 마치 0과 1로 이루어진 2진수의 배열과 똑같다는 것을 확인하셨을 겁니다. 숫자를 좀 더 써볼까요?
4 7
44 47 74 77
444 447 474 477 744 747 774 777
또 다른 규칙을 찾으셨나요? 각 자리수가 n일 때, n개의 자리수로 이루어진 숫자는 $2^n$ 개로 이루어져 있는 것을 확인할 수 있습니다. 또, $2^n$ 개의 숫자에 대해, 절반으로 나누어보면 앞자리가 4인 숫자가 절반, 7인 숫자가 절반 이렇게 이루어져 있는 것을 확인 할 수 있습니다.
결론적으로 이 문제의 풀이는 다음과 같습니다.
1. 숫자를 1, 2, 4, 8, ... 와 같이 2의 지수배로 증가시키되, k보다 커지지 않게 증가시킵니다. 숫자를 증가시키면서 k에서 빼주어 이 숫자가 몇자리의 4,7로 이루어진 수인지를 구합니다.
2. 빼고 남은 k를 2로 나누어 나머지가 0이면 4를, 7이면 7을 앞자리에 계속해서 붙여줍니다.
3. 숫자의 앞자리에 4를 자리수가 맞을 때까지 붙입니다.
앞자리에 4를 붙여주는 이유는 0,1로 이루어진 수의 경우 00000110 와 같은 수의 앞의 0을 표시하지 않지만, 4와 7로 이루어진 수에서는 붙여주어야 하기 때문입니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
int n, len=1, len2, now=2;
string ans = "";
cin >> n;
n--;
while (1)
{
if (n < now) break;
n -= now;
len++;
now *= 2;
}
while (n)
{
ans = to_string(n % 2==0 ? 4 : 7) + ans;
n /= 2;
}
len2 = ans.length();
for (; len2 < len; len2++) cout << "4";
cout << ans;
}