{0, 1, 2, 3, 4, 5}의 숫자만 사용해 만들 수 있는 수는 아래와 같습니다.
0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25, ...
이 수열은 처음 여섯 개의 숫자(0~5)를 바탕으로 일정한 규칙에 따라 차례대로 생성할 수 있습니다. 숫자가 만들어지는 과정을 예시로 살펴보겠습니다.
1 * 10 + 0 = 10 1 * 10 + 1 = 11 1 * 10 + 2 = 12 1 * 10 + 3 = 13 1 * 10 + 4 = 14 1 * 10 + 5 = 15
숫자 1뿐만 아니라 2, 3, 4, 5에도 같은 패턴을 적용하면 각각 여섯 개씩 새로운 숫자를 얻을 수 있습니다. 즉, 이미 수열에 있는 숫자에 10을 곱한 뒤 0~5를 더하는 방식으로 수열을 계속 확장해 나가는 원리입니다.
알고리즘
- 숫자 n을 초기화합니다.
- 정수를 저장할 벡터를 선언합니다.
- 0부터 5까지 반복하는 루프를 작성합니다.
- 해당 숫자들을 모두 벡터에 추가합니다.
- 이제 수열의 첫 여섯 개 숫자가 준비되었습니다.
- 0부터 n / 6까지 반복하는 루프를 작성합니다.
- 그 안에서 다시 0부터 5까지 반복하는 루프를 작성합니다.
- 앞서 설명한 패턴으로 나머지 숫자들을 생성합니다.
- 생성한 숫자들을 벡터에 추가합니다.
- 그 안에서 다시 0부터 5까지 반복하는 루프를 작성합니다.
- 수열에서 n번째 숫자를 반환합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int findNthNumber(int n) {
vector<int> numbers;
for (int i = 0; i < 6; i++) {
numbers.push_back(i);
}
for (int i = 0; i <= n / 6; i++) {
for (int j = 0; j < 6; j++) {
if ((numbers[i] * 10) != 0) {
numbers.push_back(numbers[i] * 10 + numbers[j]);
}
}
}
return numbers[n - 1];
}
int main() {
int n = 7;
cout << findNthNumber(n) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
10
n = 7일 때 수열의 일곱 번째 숫자는 10입니다. 이 방식은 숫자를 벡터에 계속 추가하면서 필요한 위치의 값만 꺼내오는 간단한 구조이므로, n이 크지 않은 경우 매우 효율적으로 동작합니다.