12. 숫자의 총 개수(large)

    12번 문제   

 

 

    내가 풀이한 답   

 

   11번 문제보다 입력 범위가 늘었다. 그래서 전 코드에서 분기문의 조건을 늘리는 작업을 했다.

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, cnt;
	scanf("%d", &n);
	
	if(n<10){
		cnt = n;
	} 
	else if(n>=10 && n<100){
		cnt = (n-9)*2 + 9;
	}
	else if(n>=100 && n<1000){
		cnt = (n-9-90)*3 + (90*2) + 9;
	}
	else if(n>=1000 && n<10000){
		cnt = (n-9-90-900)*4 + (900*3) + (90*2) + 9;
	}
	else if(n>=10000 && n<100000){
		cnt = (n-9-90-900-9000)*5 + (9000*4) + (900*3) + (90*2) + 9;
	}
	else if(n>=100000 && n<1000000){
		cnt = (n-9-90-900-9000-90000)*6 + (90000*5) + (9000*4) + (900*3) + 
		(90*2) + 9;
	}
	else if(n>=1000000 && n<10000000){
		cnt = (n-9-90-900-9000-90000-900000)*7 + (900000*6) + (90000*5) + (9000*4) + 
		(900*3) + (90*2) + 9;
	}
	else if(n>=10000000 && n<100000000){
		cnt = (n-9-90-900-9000-90000-900000-9000000)*8 + (9000000*7) + (900000*6) + 
		(90000*5) + (9000*4) + (900*3) + (90*2) + 9;
	}
	else if(n>=100000000 && n<1000000000){
		cnt = (n-9-90-900-9000-90000-900000-9000000-90000000)*9 + (90000000*8) + 
		(9000000*7) + (900000*6) + (90000*5) + (9000*4) + (900*3) + (90*2) + 9;
	}

	printf("%d", cnt);
	
	return 0;
}

 

그 결과 통과를 했지만 너무 효율성이 없다고 생각을 했다. 

 

 

 

그래서, 11번 문제의 코드를 그대로 다시 입력해봤더니 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, cnt, i, temp;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		temp = i;
		while(temp>0){
			temp /= 10;
			cnt++;
		}
	}

	printf("%d", cnt);
	
	return 0;
}

 

 결과는 범위가 10억까지 늘어서 그런지 Time Limit이 걸려서 통과하지 못했다.

 

 

 

 그래서 방법을 바꾸어 생각해보았다. 위에서 작성한 분기문을 순회(while)문을 사용해서 작성하였다. 각각의 자릿수에 해당하는 수의 개수는 9(1~9), 90(10~99), 900(100~999), 9000(1000~9999) .... 규칙적으로 10이 곱해져서 증가하는 것을 이용하였다. 

 

 

 입력받은 n의 자리수를 확인하기 위한 check 변수와 각 자리수의 숫자 개수를 확인하기 위해 임시로 사용한 temp 변수와 각 자리수를 나타내는 digit 변수를 사용해서 코드를 완성했다. 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, cnt, check = 9, digit = 1, temp = 9;
	scanf("%d", &n);
	
	if(n>=1 && n<=9){
		printf("%d", n);
		return 0;
	}
	
	while(n >= check){
		cnt += (temp*digit);
		temp = temp * 10;
		check = temp + check;
		digit++;	
	}
	check = check / 10;
	cnt += (n - check) * digit;
	
	printf("%d", cnt);
	
	return 0;
}

 

 n이 137인 경우 흐름은 다음과 같다.

 

 

코드를 채점 시스템에 적용해보니 통과를 했다.

 

 

    사이트의 답안   

#include<stdio.h>
int main(){
	//freopen("input.txt", "rt", stdin);
	int n, sum=0, cnt=1, digit=9, res=0;
	scanf("%d", &n);
	while(sum+digit<n){	
		sum=sum+digit;
		res=res+(cnt*digit);
		cnt++;
		digit=digit*10;
	}
	res=res+((n-sum)*cnt);
	printf("%d\n", res);
	return 0;
}

 

  사이트의 답안은 마지막으로 작성한 코드와 논리적으로 똑같았다.