문제 개요
숫자 N이 입력으로 주어졌을 때, 1부터 N까지의 모든 수를 나열했을 때 필요한 총 자릿수를 구하는 것이 목표입니다. 1부터 9까지는 각 숫자가 1자릿수, 10부터 99까지는 2자릿수, 100부터 999까지는 3자릿수를 차지하는 식으로 자릿수가 늘어납니다.
예제로 이해하기
입력 − N = 11
출력 − 1부터 N까지의 총 자릿수: 13
설명 − 1부터 9까지는 각각 1자릿수이므로 9자릿수이고, 10과 11은 각각 2자릿수이므로 4자릿수입니다. 따라서 총 자릿수는 9 + 4 = 13입니다.
입력 − N = 999
출력 − 1부터 N까지의 총 자릿수: 2889
설명 − 1부터 9까지는 각각 1자릿수로 9자릿수, 10부터 99까지는 각각 2자릿수로 180자릿수, 100부터 999까지는 각각 3자릿수로 2700자릿수입니다. 따라서 총 자릿수는 2700 + 180 + 9 = 2889입니다.
방법 1: 재귀 함수를 이용한 단순 접근
가장 직관적인 방법은 재귀 함수를 활용하는 것입니다. 숫자를 문자열로 변환한 뒤(to_string), 그 문자열의 길이가 곧 해당 숫자의 자릿수가 됩니다. 이 과정을 현재 숫자보다 1 작은 수에 대해 재귀적으로 반복하며 모든 자릿수를 누적합니다.
양의 정수 하나를 입력받습니다.
함수 total_digits(int num)는 num을 받아 1부터 num 사이 숫자들의 총 자릿수를 반환합니다.
num의 자릿수를 구하기 위해 to_string(num)으로 문자열을 변환합니다.
문자열의 길이가 곧 num의 자릿수입니다.
num이 1이면 1을 반환하고, 그렇지 않으면 length + total_digits(num - 1)을 반환하여 나머지 숫자들을 재귀적으로 처리합니다.
최종적으로 전체 자릿수가 결과로 반환됩니다.
방법 2: 10의 거듭제곱을 이용한 효율적 접근
두 번째 방법은 훨씬 효율적입니다. 1, 10, 100, 1000처럼 10의 거듭제곱 단위로 순회하면서, 각 단계마다 i 이상 num 이하인 수의 개수(num - i + 1)를 결과에 더합니다. 예를 들어 num = 20이라면, 한 자릿수 이상인 수는 20개(1~20), 두 자릿수 이상인 수는 11개(10~20)이므로 총 31자릿수가 됩니다.
양의 정수 하나를 입력받습니다.
총 카운트를 0으로 초기화합니다.
i를 1부터 시작해 i <= num일 때까지 매 반복마다 10배씩 늘리며, 각 단계에서 num - i + 1을 카운트에 더합니다.
반복문이 끝나면 카운트를 결과로 반환합니다.
예제 코드 (단순 접근)
#include <bits/stdc++.h>
using namespace std;
int total_digits(int num){
string str = to_string(num);
int length = str.length();
if (num == 1){
return 1;
}
return length + total_digits(num - 1);
}
int main(){
int num = 20;
cout<<"Count of total number of digits from 1 to n are: "<<total_digits(num);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of total number of digits from 1 to n are: 31
예제 코드 (효율적 접근)
#include <bits/stdc++.h>
using namespace std;
int total_digits(int num){
int count = 0;
for(int i = 1; i <= num; i *= 10){
count = count + (num - i + 1);
}
return count;
}
int main(){
int num = 20;
cout<<"Count of total number of digits from 1 to n are: "<<total_digits(num);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of total number of digits from 1 to n are: 31
마무리
재귀 기반의 단순 접근법은 이해하기 쉽지만 숫자가 커지면 재귀 호출 깊이와 반복 횟수 때문에 비효율적일 수 있습니다. 반면 10의 거듭제곱을 활용한 효율적 접근법은 O(log₁₀N) 시간 복잡도로 동작하므로 큰 N 값에서도 빠르게 결과를 얻을 수 있습니다. 실전에서는 후자의 방식을 사용하는 것이 좋습니다.