주어진 4자리 1, 2, 3, 4로 이루어진 n번째 수의 자릿수를 구해야 합니다.
위 4자리의 계열은 다음과 같습니다.
1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24...
위의 시리즈에서 n번째 숫자의 자릿수를 찾아야 합니다. 패턴을 잘 관찰하면 다음과 같은 점을 발견할 수 있습니다.
-
숫자가 1인 숫자가 4개 있습니다.
-
2자리 숫자가 16개 있습니다.
-
패턴은 4의 거듭제곱으로 계속됩니다.
예를 들어보겠습니다.
입력
7
출력
2
시리즈의 7번째 숫자는 13이고 그 숫자의 자릿수는 2입니다.
알고리즘
- 숫자 n을 초기화합니다.
- 두 개의 변수를 초기화하여 하나는 결과를 저장하고 다른 하나는 시리즈에 있는 숫자의 총합을 저장합니다.
- 반복 변수를 4의 거듭제곱으로 증가시키는 루프를 만듭니다.
- 합계 변수에 현재 숫자를 추가합니다.
- 총합이 n보다 크면 루프를 끊습니다.
- 다음 숫자 집합에는 이전 숫자 집합보다 한 자리 더 많은 숫자가 있으므로 결과에 1을 추가합니다.
- 결과를 반환합니다.
구현
다음은 위의 알고리즘을 C++로 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
int getDigitsCount(int n) {
int i, result = 1, sum = 0;
for (i = 4; ; i *= 4) {
sum += i;
if (sum >= n) {
break;
}
result += 1;
}
return result;
}
int main() {
int n = 57;
cout << getDigitsCount(n) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
3