ALLMN CTF 2019 Doesn't contain K integer

Doesn’t contain K integer

How many numbers from 1 to N that don't contain K number. Input: N (integer number) and space K (integer number).  
Output: The total number. Example if N is 30 and K is 3 there are 27 numbers that don't contain number 3.  
So the flag will be ALLMN{total number}

[문제 내용]

n = 281939942
k = 3
for i in range(n):
    if '3' in str(i):
        n -= 1
        print "total is " + str(n)

[Python]

파이썬으로 짜면 금방인 문제. 하지만 간단하면서도 간단하지 않다. 계산하는 수가 매우 높아서 소요 시간이 개노답이기 때문이다. 그래서 결국 c로 다시 뚝딱했다.^[1] c로도 약 2시간 30분이 소요 됐다. (더 빠른 알고리즘이 있겠지만 아몰랑)

#include <stdio.h>
int main(void)
{
	int num_start = 1;
	int num_end = 281939942;
	int num = 0;
	int digit = 3;
	int count = 0;

	digit %= 10;

	for (num = num_start; num <= num_end; num++) {
		int temp_num = num;
		int have = 0;
		if (num == 0) {
			if (digit == 0) {
				have = 1;
			}
		}
		else {
			while (temp_num > 0) {
				if (temp_num % 10 == digit) {
					have = 1;
					break;
				}
				temp_num /= 10;
			}
		}
		if (have == 1) {
			count++;
			if (count > 1) {
				printf(", ");
			}
			printf("%d ", num);
		}
	}
	printf("\n\ncount : %d\n", num_end-count+1);
	return 0;
}

[C]
[Run]

---

1. 1.C와 Python의 연산 속도는 약 100배가량 차이가 난다. ↩