[알고리즘 문제풀이] 12. 숫자의 총 개수(large: 제한시간 1초)★★

N이 

100,000,000까지 범위가 늘었다. 그리고 더 빨리 코드가 끝나야 한다.

 

더 큰 범위의 N을 계산하되, 제한시간을 단축하기 위해

for문을 1부터 n까지 돌리지 않고 숫자의 총 개수를 계산한 이전 11회에서 작성한 코드를 가져와보았다.

#include <stdio.h>
int main(void){
   //freopen("input.txt", "rt", stdin);
   
   // 1. 자연수를 입력 받는다.
   int n, num = 0; 
   scanf("%d", &n);	
   
   // 2. 자연수 별로 갯수를 나눈다. 
   // 1개 1-9, 2개 10-99, 3개 100-999, 4개 1000-9999, 
   // 5개 10000-99999, n은 99999까지 이므로 5개가 최대
   if(n < 10)		{ num = 1 * n; }
   else if(n < 100)	{ num = 1 * 9 + 2 * (n-9); }
   else if(n < 1000)	{ num = 1 * 9 + 2 * 90 + 3 * (n-9-90); }
   else if(n < 10000)	{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * (n-9-90-900); }
   else if(n < 100000)	{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * 9000 + 5 * (n-9-90-900-9000); }
   
   
   printf("%d\n", num); 
}

n을 늘려서 해보자

if(n < 10)			{ num = 1 * n; }
   else if(n < 100)		{ num = 1 * 9 + 2 * (n-9); }
   else if(n < 1000)		{ num = 1 * 9 + 2 * 90 + 3 * (n-99); }
   else if(n < 10000)		{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * (n-999); }
   else if(n < 100000)		{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * 9000 + 5 * (n-9999); }
   else if(n < 1000000)		{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * 9000 + 5 * 90000 + 6 * (n-99999); }
   else if(n < 10000000)	{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * 9000 + 5 * 90000 + 6 * 900000 + 7 * (n-999999); }
   else if(n < 100000000)	{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * 9000 + 5 * 90000 + 6 * 900000 + 7 * 9000000 + 8 * (n-9999999); }
   else if(n < 1000000000)	{ num = 1 * 9 + 2 * 90 + 3 * 900 + 4 * 9000 + 5 * 90000 + 6 * 900000 + 7 * 9000000 + 8 * 90000000 + 9 * (n-99999999); }

이렇게 해서 100점은 나온다. 하지만.. 너무 노가다.

 

해설을 보니 놀라웠다.

저 식을 while로 방정식을 만들었다. 계수랑 10 거듭제곱까지 이렇게 구현할 수 있구나

잘 참고해야겠다.

 

해답

#include <stdio.h>
int main(void){
   //freopen("input.txt", "rt", stdin);
   
   // 1. 자연수를 입력 받는다.
   int n, cnt = 0; 
   scanf("%d", &n);	
   int sum = 0; // 숫자의  총 갯 
   int multiple = 9;
   int c = 1;
   
   while( sum + multiple < n){
   		cnt = cnt + (c * multiple);
   		sum = sum + multiple;
   		c++;
   		multiple *= 10;
   }
   
   cnt = cnt + ((n-sum) * c);
   printf("%d\n", cnt);
}

와 다음에 다시 한번 풀어보자..