3의 개수

1~N까지 숫자중 3의 개수

#include <iostream>
#include <algorithm>
#include <vector>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;
int main() {
	//3의 개수
	
	int n,tmp,cnt=0;
	scanf("%d",&n);
	for(int i=1; i <=n; i++){
		tmp = i;
		while(tmp>0){
			if(tmp%10==3) cnt++;
			tmp/=10;
		}
	} 
	
	printf("%d",cnt);


	return 0;
}

각 자리수에서 3이 있는지 없는지 판단한다.

 

직관적이지만 시간이 오래걸린다.

 

 

--------------------------------------------

빠르게 구하려면

 

각 자리수 별로 3의 개수를 구하고 더해준다

1의 자리가 3인 갯수

10의자리가 3인 갯수

100의자리가 3인 갯수

....

 

#include <iostream>
#include <algorithm>
#include <vector>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;
int main() {
	int n, lt=-1, cur, rt, k, res=0;
	scanf("%d",&n);
	
	while(lt!=0){
		lt = n/(k*10);
		cur = (n/k)%10;
		rt = n%k;
		//printf("%d %d %d\n",lt,cur,rt);
		
		if(cur > 3) res+=(lt+1)*k;
		else if(cur <3) res+=lt*k;
		else res+=lt*k + (rt+1);
		k = k*10;
	}
	
	printf("%d",res);

	return 0;
}

 

5367
lt:536 cur:7 rt:0
537
lt:53 cur:6 rt:7
1077
lt:5 cur:3 rt:67
1645
lt:0 cur:5 rt:367
2645
2645
------