C++에서 num + Rev(num) = 10^N − 1을 만족하는 N자리 수의 개수 구하기

문제 개요

정수 N이 입력으로 주어졌을 때, num + Rev(num) = 10^N − 1을 만족하는 모든 N자리 수의 개수를 구하는 것이 목표입니다. 여기서 Rev(num)은 숫자 num의 자릿수 순서를 뒤집은 수를 의미합니다.

예시

입력

N=4

출력

num + Rev(num) = 10^N − 1을 만족하는 N자리 수의 개수는 90개입니다.

설명

해당하는 숫자들은 다음과 같습니다.

1. 1188 + 8811 = 9999
2. 2277 + 7722 = 9999
3. 1278 + 8721 = 9999
……총 90개의 숫자

입력

N=5

출력

num + Rev(num) = 10^N − 1을 만족하는 N자리 수의 개수: 0

설명

N이 홀수이면 해당하는 수는 존재하지 않습니다. 가운데 자릿수가 자기 자신과
더해지게 되는데, 같은 숫자끼리의 합은 9가 될 수 없기 때문입니다.
예: 148 + 841 = 989

접근 방법

N자리 수와 그 수를 뒤집은 수의 대응하는 자릿수끼리의 합이 모두 9라면, 두 수 전체의 합은 999…9(N개의 9), 즉 10^N − 1이 됩니다.

• N이 홀수인 경우: 가운데 자릿수는 자기 자신과 더해집니다. 같은 숫자 두 개의 합은 절대 9가 될 수 없으므로 답은 0입니다.
• N이 짝수인 경우: 첫 번째 자릿수와 N번째 자릿수, 두 번째 자릿수와 (N−1)번째 자릿수처럼 서로 대칭되는 자릿수들의 합이 9가 되어야 합니다. 가능한 조합은 (1+8), (2+7), (3+6), (4+5), (5+4), (6+3), (7+2), (8+1), (9+0)으로 총 9가지입니다.

따라서 정답은 9 × 10^{(N/2 − 1)} 공식으로 계산할 수 있습니다.

알고리즘 단계

1. 정수 N을 입력받습니다.
2. 함수 digit_numbers(int N)는 N을 받아 조건을 만족하는 N자리 수의 개수를 반환합니다.
3. count를 0으로 초기화합니다.
4. N이 홀수(N % 2 == 1)이면 0을 반환합니다.
5. 그렇지 않으면 count = 9 × pow(10, N/2 − 1)로 설정합니다.
6. count를 결과로 반환합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
int digit_numbers(int N){
    int count = 0;
    if (N % 2 == 1){
        return 0;
    } else {
        count = 9 * pow(10, N/2 - 1);
    }
    return count;
}
int main(){
    int N = 4;
    cout<<"Count of all N digit numbers such that num + Rev(num) = 10^N − 1 are: "<<digit_numbers(N);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of all N digit numbers such that num + Rev(num) = 10^N − 1 are: 90