28. UVa-725 Division //완전탐색, bitmask기법

문제

<그림1: 문제설명>

문제는 0부터 9까지 모든 수를 한 번씩 사용해서 다섯자리 정수 2개를 만들때, (0이 앞에오는 4자리수도 O.K.)

N으로 나눈 관계에 있는 두 수를 찾으라는 문제이다. 그냥 읽어보면 된다.

반복적 완전 탐색으로 풀 수밖에 없으나 어차피 100000번 이내 for문을 돌리기 때문에 괜찮을 것 같다.

그리고 각 숫자가 다 한번씩 나왔나 체크할 때 bit를 OR하는 기법을 사용했는데 꽤 유명한 기법인 것 같으니까 그것을 기억해두자. 기법의 설명은 주석에 있다.

다음은 코드다.

#include<stdio.h>
int main() {
	int N,temp,used,c=0;
	while (scanf("%d",&N) && N != 0) {
		//if N is defined, range of fghij can be calculated
		bool emerged=false;
		if (c++ > 0) printf("\n");
		for (int fghij = 1234; fghij <= 98765 / N; fghij++) {
			int abcde = fghij * N;
			used = (fghij < 10000);	//if fghij is under 10000, 0 is used in fghij
			//now have to compare
			/* How to know if all bits are between 0~9 emerged-bitwise calculation trick
			IDEA: if we make variable named 'used', 
			and change emerged digit 0~9 to 
			1<<0~1<<9, sum of all changed digit have to be 1111111111 in 2-digit system 
			thus we process used = used | 1 << (temp % 10)
			than if (temp%10)is emerged and ored before, used don't changed
			if(temp%10)is not emerged, than 1<<temp%10 is plused to used
            		->thus we get 1111111111 if 0~9 all emerged
            		->this bitmask method is faster than array-comparison method
			*/
			temp = abcde;
			while (temp) {
				used = used | 1 << (temp % 10);
				temp = temp / 10;
			}
			temp = fghij;
			while (temp) {
				used = used | 1 << (temp % 10);
				temp = temp / 10;
			}
			if (used == (1 << 10) - 1) {
				printf("%0.5d / %0.5d = %d\n", abcde, fghij, N);
				emerged = true;
			}
		}
		if (emerged == false) printf("There are no solutions for %d.\n", N);
	}
	return 0;
}