30. 3의 개수는?(large)

    30번 문제   

 

 

---

    내가 풀이한 답   

  앞의 문제와 동일한 코드로 채점해봤지만 역시 Time_Limit이 났다. 

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

 

 순회문(for, while) 하나로 작성하기에는 어떤 특정한 논리가 필요한데 생각나지 않아서 강의 초반부를 참고했다. 논리는 다음과 같다. 

 

 핵심은 자리 수를 기준으로 입력받은 수를 left, cur, right로 구분하고 cur의 숫자에 따라 공식이 달라진다는 것이다. 위의 아래 그림에서 k가 10이므로 cur은 10의 자리 숫자를 가리킨다.(아래 그림에선 각각 7, 3, 1) 이 cur을 기준으로 왼쪽은 left, 오른쪽은 right로 설정한다. 그리고 cur을 기준으로 공식을 설정한다. 

 

 

 4377을 예로 들면 흐름은 다음과 같다. 

 

---

    사이트의 답안   

#include<stdio.h>
int main(){
	//freopen("input.txt", "rt", stdin);
	int n, left=77, right, cur, k=1, res=0;
	scanf("%d", &n);
	
    while(left != 0){
		left=n/(k*10);
		right=n%k;
		cur=(n/k)%10;
		if(3<cur){
			res=res+((left+1)*k);
		}
		else if(3==cur){
			res=res+((left*k)+(right+1));
		}
		else res=res+(left*k);	
		k=k*10;
	}
	
    printf("%d\n", res);
	return 0;
}