[알고리즘 문제풀이] 11. 숫자의 총 개수(small)★

 

100점 맞은 코드지만 n 이 100,000 이상으로 커지면 비효율적인 코드이다.

n의 자릿수 별로 노가다로 일일히 수식을 구했다.

#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); 
}

좀 더 간단히 만들어서 

#include <stdio.h>
int main(void){
   //freopen("input.txt", "rt", stdin);
   
   // 1. 자연수를 입력 받는다.
   int n, num = 0; 
   scanf("%d", &n);	
   
   // 2. 자연수 별로 갯수를 나눈다. 
   for(int i = 1; i <= n; i++){
   	if(i < 10) num += 1;
   	else if(i < 100) num += 2;
   	else if(i < 1000) num += 3;
   	else if(i < 10000) num += 4;
   	else if(i < 100000) num += 5;
   }
   printf("%d\n", num); 
}

여기서 156468746564352413246546... 처럼 n이 무한히 커진다고 할 때 코드를 짜보자

10 을 생각해보면 10^1 ≤ 10＜ 10^2 이고 num += 2 이므로 식을 세워보면

10^(j -1) ≤ n ＜ 10^j 일 때 num += j  이용

 

거듭제곱은 ^ 으로 계산할 수 없다.

#include <math.h>

if( pow(10,j-1) <= i && i < pow(10,j)) {num += j; break;}

pow(밑, 지수) 를 이용해주자.

 

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

int main(void){
   //freopen("input.txt", "rt", stdin);
   
   // 1. 자연수를 입력 받는다.
   int n, num = 0; 
   scanf("%d", &n);	
   
   // 2. 자연수 별로 갯수를 나눈다. 
   for(int i = 1; i <= n; i++){
   	for(int j = 1; j < 10; j++){
   		
   		if( pow(10,j-1) <= i && i < pow(10,j)) {
   			num += j;
   			printf("i가 %d:	자릿수는 %d\n", i, j);
   			break;
		   }
   		
	   }
   }
   printf("%d\n", num); 
}

결과가 잘 나온다.

해답을 보니 완전 다르게 짜셨다.. 아니 ㅠㅜ 나눗셈을 이용해서 풀다니

pow()를 이용할 필요가 없었다.

n을 10으로 반복해서 나눈 나머지가 0이 될 때까지 카운트한다.

 

해답

#include <stdio.h>

int main(void){
   //freopen("input.txt", "rt", stdin);
   // 1. 자연수를 입력 받는다.
   int n, cnt = 0; 
   scanf("%d", &n);	
   
   // 2. 1~n까지 10 거듭제곤으로 나눈 나머지가 0이 될 때까지 1씩 증가한다. 
   for(int i = 1; i <= n; i++){
	   	int tmp = i;
	   	while( tmp > 0){
		   		tmp = tmp / 10; 
		   		cnt++;
		   }
	}
   printf("%d\n", cnt); 
}

 

주의할 점

i 변수를 이용하여 나누면 i=0이 되여 for문이 무한루프로 갇히게 된다.

그러므로 tmp 임시 변수에 for이 시작하자마자

tmp = i 를 넣어서 i값을 따로 변수에 빼서 쓰자.

이것 때문에 30분 간 printf로 출력값 구하면서 해맸다