문제 개요
자릿수를 나타내는 숫자 d가 주어집니다. 목표는 최대 d자릿수이면서 숫자 0을 적어도 하나 포함하는 양의 정수의 개수를 구하는 것입니다. 즉, 1자릿수, 2자릿수, 3자릿수 … d자릿수인 모든 양의 정수 중 0이 하나라도 들어 있는 수를 전부 세어야 합니다.
수학적 배경
먼저 “d자릿수이면서 0을 적어도 하나 포함하는 수”가 몇 개인지 구해 보겠습니다. 예를 들어 d=3일 때, 0을 하나 이상 포함하는 3자릿수를 만들 수 있는 경우의 수는 다음과 같습니다.
백의 자리(d1): 1~9 → 9가지 십의 자리(d2): 0~9 → 10가지 일의 자리(d3): 0~9 → 10가지 만들 수 있는 전체 3자릿수: 9 × 10 × 10 = 9 × 10² 일반화하면, · d자릿수 전체 개수: 9 × 10^(d−1) · d자릿수 중 0이 하나도 없는 수: 9^d ∴ d자릿수 중 0을 적어도 하나 포함하는 수 = 9 × 10^(d−1) − 9^d = 9 × (10^(d−1) − 9^(d−1))
예제로 확인하기
입력: d = 4
출력: 0을 자릿수로 포함하는 최대 'd'자릿수 양의 정수의 개수 = 2619
설명: 자릿수별로 0을 하나 이상 포함하는 수의 개수는 다음과 같습니다.
1자릿수 : 0개 2자릿수 : 9개 3자릿수 : 171개 4자릿수 : 2439개 합계 = 9 + 171 + 2439 = 2619
입력: d = 1
출력: 0을 자릿수로 포함하는 최대 'd'자릿수 양의 정수의 개수 = 0
설명: 1부터 9까지의 한 자릿수에는 0이 포함될 수 없습니다.
방법 1: 반복문을 이용한 단순 접근
가장 직관적인 방법은 for 반복문을 사용하는 것입니다. 1자릿수부터 d자릿수까지 차례대로 순회하면서 앞서 유도한 공식으로 각 자릿수의 개수를 계산하고, 그 값을 결과에 누적합니다.
- 자릿수 d를 입력받습니다.
- 함수
total_count(int d)는 d자릿수 중 0을 적어도 하나 포함하는 수의 개수를 반환합니다. - 공식 temp = 9 × (pow(10, d−1) − pow(9, d−1)) 로 개수를 계산합니다.
- temp를 반환합니다.
- 함수
maximum_d(int d)는 최대 d자릿수까지 0을 포함하는 수의 총 개수를 반환합니다. - 1자릿수부터 시작하여 2, 3, … d자릿수까지 반복문으로 순회합니다.
- 각 i에 대해 total_count(i)를 계산해 count에 더합니다.
- 반복이 끝나면 전체 개수 count를 결과로 반환합니다.
방법 2: 등비수열을 활용한 효율적 접근
위의 합계 과정에서 등비수열(G.P.)이 만들어진다는 점을 이용하면, 반복문 없이 한 번의 계산으로 답을 구할 수 있습니다.
전체 합 = Σ [9 × (10^(i−1) − 9^(i−1))] (1 ≤ i ≤ d)
= {9 × (10^d − 1) ÷ (10 − 1)} − {9 × (9^d − 1) ÷ (9 − 1)}
= (10^d − 1) − (9/8) × (9^d − 1)
- 최대 자릿수 d를 입력받습니다.
- 함수
maximum_d(int d)는 최대 d자릿수까지 0을 포함하는 수의 총 개수를 반환합니다. - temp_1 = 9 × ((pow(10, d) − 1) / 9) 로 첫 번째 등비수열의 합을 계산합니다.
- temp_2 = 9 × ((pow(9, d) − 1) / 8) 로 두 번째 등비수열의 합을 계산합니다.
- count = temp_1 − temp_2 를 설정합니다.
- count를 결과로 반환합니다.
예제 코드 (단순 접근)
#include<bits/stdc++.h>
using namespace std;
int total_count(int d){
int temp = 9*(pow(10,d-1) - pow(9,d-1));
return temp;
}
int maximum_d(int d){
int count = 0;
for (int i=1; i<=d; i++){
count = count + total_count(i);
}
return count;
}
int main(){
int d = 5;
cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of positive integers with 0 as a digit and maximum 'd' digits are: 33570
예제 코드 (효율적 접근)
#include<bits/stdc++.h>
using namespace std;
int maximum_d(int d){
int temp_1 = 9*((pow(10,d)-1)/9);
int temp_2 = 9*((pow(9,d)-1)/8);
int count = temp_1 - temp_2;
return count;
}
int main(){
int d = 4;
cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of positive integers with 0 as a digit and maximum 'd' digits are: 2619
마무리 및 참고 사항
두 방법 모두 동일한 결과를 내지만, 단순 접근은 O(d)번의 반복이 필요한 반면 등비수열 공식을 활용한 효율적 접근은 상수 시간에 답을 구할 수 있어 d가 클 때 특히 유리합니다. 다만 pow 함수는 부동소수점 연산을 수행하므로 d가 매우 커지면 오차가 발생할 수 있으며, 이 경우 정수 거듭제곱을 직접 구현하거나 오버플로우 범위를 고려한 자료형(예: long long)을 사용하는 것이 안전합니다.