스테핑 숫자는 연속된 자릿수의 차이가 1인 숫자입니다. 자릿수를 나타내는 숫자 n이 주어집니다. n자리의 스테핑 숫자의 총 수를 계산해야 합니다.
예를 들어 보겠습니다.
입력
2
출력
17
2자리의 가장 작은 수는 10이고, 가장 높은 2자리의 수는 99입니다. 그 사이에는 17개의 스테핑 숫자가 있습니다.
알고리즘
- 숫자 n을 초기화합니다.
- 카운트를 0으로 초기화합니다.
- pow(10, n - 1)와 같이 n자리의 가장 작은 수를 찾습니다.
- n자리 중 가장 높은 수를 찾습니다. 즉, pow(10, n) - 1입니다.
- 가장 낮은 n자리 숫자에서 가장 높은 n자리 숫자까지 반복하는 루프를 작성하세요.
- 현재 번호가 스테핑 번호인지 확인하십시오.
- 숫자에서 연속된 숫자 쌍의 차이를 확인합니다.
- 차이의 결과가 1이 아닌 경우 false else true를 반환합니다.
- 현재 숫자가 스테핑 숫자인 경우 카운트를 증가시킵니다.
- 카운트를 반환합니다.
구현
다음은 위의 알고리즘을 C++로 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
bool isSteppingNumber(int n) {
int previousDigit = -1;
while (n) {
int currentDigit = n % 10;
if (previousDigit != -1 && abs(previousDigit - currentDigit) != 1) {
return false;
}
previousDigit = currentDigit;
n /= 10;
}
return true;
}
int getSteppingNumbersCount(int n) {
int lowestNumber = pow(10, n - 1), highestNumber = pow(10, n) - 1;
int count = 0;
for (int i = lowestNumber; i <= highestNumber; i++) {
if (isSteppingNumber(i)) {
count += 1;
}
}
return count;
}
int main() {
int n = 3;
cout << getSteppingNumbersCount(n) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
32