간단해 보이지만..사실은 정말 어려운 문제에 봉착했습니다. C언어..

k개의 숫자가 주어졌을 때, 중복을 허용하여 r개의 숫자를 뽑아서 나열하는 가지수는 중복순열(k^r)로 구할수 있습니다.
등비수열이므로, 최대 r개까지 뽑아서 만들수 있는 총수
S(r) = k + k^2 + k^3 + ... + k^r
은 쉽게 구할수 있구요. 공식은 아마 k(1-k^r)/(1-k) 였던거 같은데, 지금 확실히 기억하는 건 아니고,
도출도 간단하므로, 고등학교 수학1에서 등비수열의 합(등비급수)을 찾아보세요.
S(r)이 주어진 인덱스보다 커지는 최초의 r을 구해서, S(r-1)에 인덱스까지 남은 갯수 구해서 더하면 될것 같습니다.

지금보니, 인덱스에 해당하는 문자열을 반환하는 것이므로, 그냥 남은 갯수 그 자체가 반환할 문자열이 되겠군요.
0부터 세고 있어서 남은 갯수 그 자체인지, +1이나 -1되는지 지금 생각해보기가 귀찮지만 그건 조금해보시면 금방 알수 있을 거 같구요...
남은 갯수에 앞에 0채워서 내보내면 될거 같습니다.

3진수로.. n번째 군의 시작위치는 3(3^(n-1)-1)/2 이고요. 따라서 k번째 위치의 수를 알고 싶으면 3(3^(n-1)-1)/2 <= k < 3(3^n-1)/2 인 n을 찾고 그 군에서 k의 위치를 찾아서 3진수로 만들고 앞에 0을 붙이면 됩니다. 이때 n은 로그연산으로 상수시간에 찾을 수 있고요. 3말고 임이의 개수에 대해서도 같은 방법으로 하면 되고요.

비슷한 문제로 http://121.182.65.78/30stair/luckynum/luckynum.php?pname=luckynum&stair=3 이게 있고요, 이 문제에 대해 다음과 같은 풀이가 가능합니다.

#include <iostream>
#include <cmath>
int main(){
int a;
std::cin >> a;
int n=(int)(log(a)/log(2));
int m = a-pow(2,n)+1;
std::string s(n,'4');
int i=0;
while(m)
{
if(m&0x01){
s[n-i-1]='7';
}
m>>=1;
i++;
}
std::cout << s;
return 0;
}

더 원하신다면 여기에 댓글 달아 주세요. 자고 일어나서 도와 드리겠습니다. 근데 글의 예제에서 9번째 이후에 2 0, 2 1, 2 2 이어야 할것 같은데 맞나요?

문자셋이 3개면 3진수일테고.. 5개면 5진수일테고..
그냥 진수 변환으로밖에 안보이는데
문제가 잘 이해가 안되요..;;