[C++] 3의 개수 (시간 제한)

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개 있는지 구하려고 합니다.
예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다.
첫 줄에 자연수의 개수 N(3<=N<=1,000,000,000)이 주어집니다.

#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
		// 자릿수(cur)를 기준으로 right(나머지부분), left(몫 부분)
	int left = 1, right, cur, k = 1, ans = 0;
	while (left != 0) {
		left = n / (k * 10);
		right = n % k;
		cur = (n / k) % 10;

			// 만약 12345 이면 온전하게 12300~12345를 가져갈 수 없음.  
			// 300 ~ 11300 을 온전하게 가져가고 나머지 12300 ~12345 에 대해서 처리
		if (cur > 3) { ans = ans + ((left + 1)*k); }
		else if (cur == 3) { ans = ans + (left*k) + (right + 1); }
			// 3보다 작은 경우 1000의 자리는 10000의 자리 개수만큼 있음 12345 -> 03000~ 03999
		else { ans = ans + (left *k); }
		k = k * 10;
	}
	printf("%d", ans);
}

 

1부터 N까지 for문을 돌려서 3이 몇개 들어가는지 카운팅하는 방법도 있지만, N이 커지면 for문 횟수가 기하급수적으로 커진다. 

 

시간 초과를 피하기 위해서 아래와 같은 규칙을 적용했다.

 

일의 자리, 십의 자리, 백의 자리... 나눠서 개수를 구해야 한다.

12345 라는 값이 들어온 경우,

일의 자리에 3이 들어간 경우는  3 , 13, 23, ~ , 12323, 12333, 12343 으로 1234 + 1개

십의 자리는 30, 130, 230, ~ 12230, 12330 으로 123 + 1개

백의 자리는 300, 1300, 2300, ~ , 11300 으로 12개

천의 자리는 3000으로 1개

만의 자리는 3보다 작으므로, 만의 자리에 3이 들어갈 수 없다.

이 값들을 n에서 각 자릿수만큼 나눈 몫으로 생각하여 left 변수에 담는다.

 

 

그 다음에는 위에서 구한 left 값에 각 자릿수 만큼 곱해야 한다.

예를 들어, 백의 자리가 3인 경우 300 ~ 399 도 카운팅되야한다.

일의 자리 = 1235 * 1

십의 자리 = 123 * 10

백의 자리 = 12 * 100

천의 자리 = 1 * 1000

 

 

마지막으로는 애매하게 남은 숫자를 처리해야한다.

백의 자리를 조사하는 경우 300, 1300, ~ 11300 이외에도 12300 ~ 12345 의 값들도 포함되어야 한다.

남는 숫자들은 n을 각 자릿수 만큼 나눈 나머지 값으로 right 변수에 담는다. 

0부터 시작했으므로 right 값에 1을 더해야 한다.

 

이런 식으로 자릿수가 3보다 작은 경우, 3인 경우, 3보다 큰 경우 나눠서 생각해야 한다.

3보다 작다면 위에서 구한 left 값을 그대로 사용하고,

3과 같다면 left 값에 right 값도 더한다.

3보다 크다면 left + 1 값을 사용한다.