[c++] 복면산 SEND+MORE=MONEY

복면산 문제

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[10], ch[10];
int send() {
	return a[6]*1000+a[1]*100+a[3]*10+a[0];
}
int more() {
	return a[2]*1000+a[4]*100+a[5]*10+a[1];
}
int money() {
	return a[2]*10000+a[4]*1000+a[3]*100+a[1]*10+a[7];
}
void DFS(int L) {
	if(L==8) {
		if(send()+more()==money()){
			if(a[2] == 0 || a[6] == 0) return;
			printf("  %d %d %d %d\n", a[6], a[1], a[3], a[0]);
			printf("+ %d %d %d %d\n", a[2], a[4], a[5], a[1]);
			printf("---------\n");
			printf("%d %d %d %d %d\n", a[2], a[4], a[3], a[1], a[7]);
		}
	}
    else {
		for(int i=0; i<10; i++){
			if(ch[i]==0){
				a[L]=i;
				ch[i]=1;
				DFS(L+1);
				ch[i]=0;
			}
		}
	}
}
int main() {
	//freopen("input.txt", "rt", stdin);
	DFS(0);
	return 0;
}

 

** 복면산이란

복면산 문제는 특별한 언급이 없는 한, 같은 문자는 같은 숫자를 나타내고 서로 다른 문자는 서로 다른 숫자를 나타내는 것으로 생각하며, 첫 번째 자리의 숫자는 0이 아니라고 가정하는 것이 보통이다. 또한, 대개의 경우 복면산 문제의 답은 유일해야 한다.

 

위의 정의에 따라서 a배열에 SEND, MORE, MONEY에 포함되는 문자를 하나씩 정의해둔다.

그 후 send, more, money문자에 해당하는 a배열의 값에 따라 숫자를 도출하는 함수를 하나씩 선언한다.

그런다음 하나씩 조합해가며 순열을 만들어준다.

a배열에 하나씩 숫자를 배치하면서 DFS를 통해 가지를 뻗어나간다.

a배열에 지정한 문자에 숫자를 하나씩 배정하면 배정된 숫자를 프린트해준다.