숫자의 총 개수( 큰 수 ver. 제한시간 ) C++

앞 글의 문제와 같으나 이번에는 입력 값의 범위가 100,000,000 으로 변경되었다.

값이 이렇게 커지면 역시나 시간초과가 발생하지 않도록 최대한 효율적으로 작성해야한다.

 

한자리 -> 1 ~ 9 : 9개

두 자리 -> 10 ~ 99 : 90개

세 자리 -> 100 ~ 999 : 900개

9에서 자릿수만큼 10을 계속 곱한 것으로 규칙을 알 수 있다. 

 

값이 딱 9, 99, 999 라면 나머지 숫자들을 계산하지 않아도 되지만

245 를 예로 들자면 1 ~9 (9개), 10 ~ 99 (90개), 100 ~ 245 (146개) 로 세자리 수의 경우 900을 채우지 못한다.

 

c : 자릿수 d : 각 자릿수에 해당하는 숫자의 갯수 res : 총 개수 sum : 누적 개수

 

sum(0) + d (9) < num (245) 가 성립된다. 즉 1의 자리는 넘는다,245가 입력된다면, 

res 에 1의 자리에 대한 숫자의 개수를 더한다.

sum += d 를 하여 값이 9가 된다. 이것은 while문의 조건에 사용된다.

c++ : 두자리 숫자로 넘어간다.

d : 두자리 숫자에 해당하는 갯수는 90개이므로.. 10을 곱한다.

 

다시 while문 sum(9) + d(99) < num(245) 성립한다. 99보다 크다는 것이므로 두자리의 숫자 개수를 더해준다.

위와 같은 코드가 실행되어 sum = 99, res = 189, c = 3, d = 900이 된다.

 

세자리 수로 넘어와 while문을 진행한다. sum(99) + d(900) < num(245) 성립되지 않는다. 즉 999보다는 작다.

그러면 남은 세자리 숫자들을 계산해야한다.

한 자리 9, 두 자리 90 = 99 그러면 세 자리에 해당되는 숫자는 num(245) - sum(99)가 된다. 

남은 숫자에 해당하는 자릿수(c)만큼 곱한 값을 res에 더해줘서 최종 값을 구한다.

#include<stdio.h>
#include<math.h>

int main() {
	int num, sum = 0;
	int c = 1; 
	int d = 9;
	int res = 0;
	scanf("%d", &num);
	while (sum + d < num) {
		res = res + (c*d);
		sum = sum + d;
		c++;
		d = d * 10;
	}
	res += (num - sum)*c;
	printf("%d", res);
}