문제

SEND + MORE = MONEY에 해당하는 복면산을 구하는 프로그램을 작성하시오.
(복면산은 문자를 이용하여 표현된 수식에서, 각 문자가 나타내는 숫자를 알아내는 문제이다.)

• 출력예시
  

풀이

각 문자가 나타내는 숫자를 알아내는 문제이다.
따라서 문제에 쓰이는 알파벳을 순서대로 두고, 각 알파벳에 번호를 부여하고 이를 배열로 생각하였다.

DEMNORSY
01234567

결국 0~9까지의 숫자중 위의 알파벳 배열에 해당하는 숫자를 찾아내는 것으로,
순열을 조합하는 문제로 생각하였다.

따라서 DFS로 풀이하였다.

main함수 부분을 시작점으로 한다. DFS의 Level은 0부터 시작한다고 생각
a배열 : 각 문자에 해당하는 숫자를 표시하기 위함이다.
ch배열 : 0~9까지의 숫자중 어떤것을 사용했는지 체크하기 위함이다.

#include <iostream>
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 Level) {
    if(Level==8) {		// 종료 조건
        if(send() + more() == money()) {
            if(a[6] == 0 || a[2] == 0) return;		
            // 숫자의 시작이 0이 되는 부분은 제외
            // ex) MONEY와 MORE의 M & SEND의 S
            else {
                cout << "  "<< a[6] << " " << a[1] << " " << a[3] << " " << a[0] <<"\n";
                cout << "+ " << a[2] << " " << a[4] << " " << a[5] << " " << a[1] <<"\n";
                cout << "-----------\n";
                cout << a[2] << " " << a[4] << " " << a[3] << " " << a[1] <<" " << a[7] << "\n";
            }
        }
    }
    else {
        for(int i=0; i<=9; i++) {		// 0부터 9까지
            if(ch[i]==0) {		// 안썼다면
                a[Level] = i;		// 쓰고, a[Level]에 해당하는 숫자가 i라고 생각
                ch[i] = 1;		// 썼다고 체크
                DFS(Level+1);		// 다음 자리수로 이동
                ch[i] = 0;
            }
        }
    }
}
int main() {
    DFS(0);
    return 0;
}

• 결과 출력