[C++] DFS - MS인터뷰 복면산(SEND + MORE = MONEY)

using namespace std;
 
int a[10], ch[10];
 
int send() {
    return a[0]*1000+a[1]*100+a[2]*10+a[3];
}
 
int more() {
    return a[4]*1000+a[5]*100+a[6]*10+a[1];
}
 
int money() {
    return a[4]*10000+a[5]*1000+a[2]*100+a[1]*10+a[7];
}
 
void DFS(int L) {
    if(L==8) {
        if(send()+more()==money()){
            if(a[0] == 0 || a[4] == 0) return;
            printf("  %d %d %d %d\n", a[0], a[1], a[2], a[3]);
            printf("+ %d %d %d %d\n", a[4], a[5], a[6], a[1]);
            printf("---------\n");
            printf("%d %d %d %d %d\n", a[4], a[5], a[2], 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() {
    DFS(0);
 
    return 0;
}

• S E N D M O R Y 이 7개의 문자가 각각 어떤 수를 가지고 있어야 SEND + MORE = MONEY라는 공식에 성립되는지를 판단해야 한다.
• 따라서, 각 문자는 0 ~ 9라는 숫자를 가질 수 있으므로 모든 경우의 수에 따라서 계산을 수행해야하는 것이다.
• 모든 경우의 수를 알아야하므로, DFS로 백트레킹을 해야하는 문제가 된다.
• 풀이 자체는 매우 간단하다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard