숫자 N이 입력으로 주어졌을 때, 자릿수에 포함된 0의 개수가 짝수인 모든 N자리 숫자의 개수를 구하는 것이 이 문제의 목표입니다. 여기서는 앞자리 0(선행 0)도 허용합니다. 예를 들어 N=3이라면 001, 002, 003 … 010 … 처럼 0으로 시작하는 숫자들까지 모두 포함됩니다.
구체적인 예시를 통해 살펴보겠습니다.
입력 − N=4
출력 − 0이 짝수 개 포함된 N자리 숫자의 개수 − 7047
설명 − 4자리 숫자들은 다음과 같이 구성됩니다.
가장 작은 수는 0000이며, 그다음은 0011, 0012, 0013, 0014… 순서로 이어지고 가장 큰 수는 9900입니다.
입력 − N=5
출력 − 0이 짝수 개 포함된 N자리 숫자의 개수 − 66383
설명 − 5자리 숫자들은 다음과 같이 구성됩니다.
가장 작은 수는 00001이며, 그다음은 00002, 00003, 00004… 순서로 이어지고 가장 큰 수는 99900입니다.
풀이 접근 방식
이 문제는 전체 경우의 수에서 0이 홀수 개 포함된 경우를 빼는 방식으로 효율적으로 해결할 수 있습니다. 먼저 전체 N자리 숫자의 개수를 T = 10N − 1로 계산하고, 0이 홀수 개 포함된 N자리 숫자의 개수를 O = 10N − 8N으로 구합니다. 그러면 0이 짝수 개 포함된 숫자의 개수는 T − O/2가 됩니다.
여기서 8N이 등장하는 이유는 이항정리 덕분입니다. 길이 N의 모든 숫자열(총 10N개) 가운데 0이 짝수 개인 경우와 홀수 개인 경우의 개수 차이는 (9−1)N = 8N이 되므로, 홀수 개수는 (10N − 8N) / 2로 계산됩니다.
정수 N을 입력으로 받습니다.
count_even(int N) 함수는 N을 인자로 받아 0이 짝수 개 포함된 N자리 숫자의 개수를 반환합니다.
전체 N자리 숫자의 개수는 total = pow(10, N) − 1 입니다.
0이 홀수 개 포함된 N자리 숫자의 개수는 odd = pow(10, N) − pow(8, N) 입니다.
0이 짝수 개 포함된 나머지 숫자의 개수는 even = total − odd / 2 로 계산됩니다.
even 값을 최종 결과, 즉 0이 짝수 개 포함된 N자리 숫자의 개수로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int count_even(int N){
int total = pow(10, N) - 1;
int odd = pow(10, N) - pow(8, N);
int even = total - odd / 2;
return even;
}
int main(){
int N = 3;
cout<<"Count of Numbers with N digits which consists of even number of 0's are: "<<count_even(N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of Numbers with N digits which consists of even number of 0's are: 755
참고 사항
pow() 함수는 내부적으로 부동소수점 연산을 수행하므로 N이 커질 경우 정밀도 오류나 int 타입의 오버플로우가 발생할 수 있습니다. 더 큰 N을 안전하게 다루려면 long long 타입을 사용하거나 반복문으로 거듭제곱을 직접 계산하는 방식을 권장합니다. 알고리즘 자체의 시간 복잡도는 pow 연산에 좌우되며 대략 O(log N) 수준으로 매우 효율적입니다.