자릿수의 합이 10이 되는 수들을 나열하면 다음과 같습니다.
19, 28, 37, 46, 55, 64, 73, 82, 91, ...
이 수열을 자세히 관찰해 보면 각 수가 9씩 증가한다는 규칙을 발견할 수 있습니다. 물론 9씩 증가하는 과정에서 자릿수의 합이 10이 아닌 수도 등장하지만(예: 91 다음의 100은 자릿수의 합이 1), 그렇다 하더라도 자릿수의 합이 10인 모든 수는 이 탐색 과정에서 반드시 만나게 됩니다.
그 이유는 수학적으로도 설명할 수 있습니다. 어떤 수의 자릿수 합이 10이라면, 그 수를 9로 나눈 나머지는 항상 1입니다. 시작점인 19 역시 9로 나누면 나머지가 1이므로, 19부터 9씩 더해가면 자릿수의 합이 10일 가능성이 있는 모든 후보 수를 빠짐없이 확인할 수 있습니다.
따라서 9씩 증가하는 반복문을 작성하고, 각 단계마다 자릿수의 합을 검사하여 n번째 수를 찾으면 됩니다. 몇 가지 예시를 살펴보겠습니다.
입력 예시
3 7
출력 예시
37 73
알고리즘
- 찾고자 하는 순번 n을 초기화합니다.
- 카운터를 0으로 초기화합니다.
- 19부터 시작하는 반복문을 작성합니다.
- 현재 수의 자릿수 합이 10이면 카운터를 1 증가시킵니다.
- 카운터가 n과 같아지면 현재 수를 반환합니다.
- 반복 변수를 9씩 증가시킵니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int findNthNumber(int n) {
int count = 0, i = 19;
while (true) {
int sum = 0;
for (int number = i; number > 0; number = number / 10) {
sum = sum + number % 10;
}
if (sum == 10) {
count++;
}
if (count == n) {
return i;
}
i += 9;
}
return -1;
}
int main() {
int n = 7;
cout << findNthNumber(7) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
73
즉, n이 7일 때 자릿수의 합이 10이 되는 일곱 번째 수는 73임을 확인할 수 있습니다. 이 접근 방식은 9씩 건너뛰며 후보를 좁혀 가기 때문에, 모든 자연수를 하나씩 검사하는 방법에 비해 약 9배 적은 연산 횟수로 답을 찾을 수 있다는 장점이 있습니다.