Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 특정 조건을 만족하는 모든 N자리 숫자의 개수 구하기

이 튜토리얼에서는 주어진 조건을 만족하는 N자리 숫자의 개수를 구하는 프로그램을 C++로 작성하는 방법을 알아봅니다.

문제 이해하기

하나의 정수 N이 주어졌을 때, 다음 조건을 만족하는 N자리 숫자가 몇 개인지 구하는 것이 우리의 과제입니다.

숫자 + 뒤집은 숫자(Reverse) = 10N − 1

여기서 10N − 1은 N개의 9로 이루어진 수를 의미합니다. 예를 들어 N이 4라면, 어떤 4자리 수와 그 수를 거꾸로 뒤집은 수를 더했을 때 9999가 되어야 한다는 뜻입니다.

접근 방법

두 수의 합이 모든 자릿수가 9가 되려면 덧셈 과정에서 받아올림(carry)이 발생하지 않아야 하고, 앞쪽 i번째 자릿수와 뒤쪽 i번째 자릿수의 합이 정확히 9가 되어야 합니다. 이 성질을 이용하면 경우의 수를 다음과 같이 정리할 수 있습니다.

  • N이 홀수인 경우: 가운데 자릿수는 자기 자신과 더해져 9가 되어야 하는데, 2 × d = 9를 만족하는 정수는 존재하지 않습니다. 따라서 답은 0입니다.
  • N이 짝수인 경우: 첫 번째 자릿수는 N자리 수가 되어야 하므로 1~9 사이에서 9가지 선택이 가능하고, 나머지 N/2 − 1개의 자릿수 쌍은 각각 10가지씩 자유롭게 선택할 수 있습니다. 따라서 답은 9 × 10(N/2 − 1), 즉 9 뒤에 (N/2 − 1)개의 0이 붙는 형태입니다.

예를 들어 N = 4일 때 답은 9 × 10 = 90입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 조건을 만족하는 숫자의 개수를 반환하는 함수
string count_num(int N){
    // N이 홀수이면 조건을 만족하는 수가 없음
    if (N % 2 == 1)
        return "0";
    string result = "9";
    // 9 뒤에 (N/2 - 1)개의 0을 이어 붙임
    for (int i = 1; i <= N / 2 - 1; i++)
        result += "0";
    return result;
}

int main(){
    int N = 4;
    cout << count_num(N);
    return 0;
}

출력 결과

90

코드 설명

N이 커지면 결과값도 매우 빠르게 증가하므로(예: N = 40이면 20자리 숫자가 됨) 오버플로우를 피하기 위해 정수형 대신 문자열로 결과를 저장합니다. 먼저 N이 홀수인지 검사하여 홀수라면 즉시 "0"을 반환하고, 짝수라면 "9"로 시작한 뒤 N/2 − 1번 반복하면서 "0"을 이어 붙여 최종 답을 완성합니다. 시간 복잡도는 O(N)으로 매우 효율적입니다.