[Inflearn] 복면산 SEND+MORE=MONEY (MS interview source)

#. Problem

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

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

복면산이 처음에 뭔가.. 했다.

위키백과에 따르면 "복면산은 수학 퍼즐의 한 종류로, 문자를 이용하여 표현된 수식에서 각 문자가 나타내는 

숫자를 알아내는 문제"라고 한다.

숫자 대부분을 문자로 숨겨서 나타내므로 숫자가 "복면"을 쓰고 있는 연산이라는 뜻에서 복면산이라 이름이 지어졌다고 한다.

  - 복면산 문제는 특별한 언급이 없는 한, 같은 문자는 같은 숫자를 나타내고 

    서로 다른 문자는 서로 다른 숫자를 나타내는 것으로 생각하며, 

    첫 번째 자리의 숫자는 0이 아니라고 가정하는 것이 보통

  - 대개의 경우 복면산 문제의 답은 유일해야 함

//

한마디로 0~9 까지의 숫자를 사용해서

SEND + MORE = MONEY 를 만족하는 문자의 정체(?)를 알아내는 것이 목적인듯 하다.

우선 SEND, MORE, MONEY 에는 알파벳 S,E,N,D,M,O,R,Y 가 사용된다.

이 문자를 배열의 각 idx로 사용한다고 했을 때,

0	1	2	3	4	5	6	7
S	E	N	D	M	O	R	Y

라고 할 수 있겠다.

이때, 각 idx에 0~9까지의 숫자를 넣어보는데,

아래와 같이 1~8까지 넣었다고 해보자.

0	1	2	3	4	5	6	7
S	E	N	D	M	O	R	Y
1	2	3	4	5	6	7	8

그렇다면,

SEND = 1234

MORE = 5672

MONEY = 56328

가 되겠다.

그러면 SEND + MORE = MONEY 를 만족하는가?

SEND + MORE는 6906 이지만 MONEY는 56328 이다.

만족하지 않는 것이다.

이렇게 0~9까지의 숫자를 조합해보면서 SEND + MORE = MONEY 를 만족하는 각 문자에 해당하는 숫자를 찾는 것이다.

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define f first
#define s second
#define MAX 2147000000
#define MIN -2147000000
 
int rst[10], ch[10];
 
int Send()
{
    return rst[0] * 1000 + rst[1] * 100 + rst[2] * 10 + rst[3];
}
 
int More()
{
    return rst[4] * 1000 + rst[5] * 100 + rst[6] * 10 + rst[1];
}
 
int Money()
{
    return rst[4] * 10000 + rst[5] * 1000 + rst[2] * 100 + rst[1] * 10 + rst[7];
}
 
void DFS(int lv)
{
    int i;
    if (lv == 8)
    {
        if (Send() + More() == Money())
        {
            if (rst[0] != 0 && rst[4] != 0)
            {
                printf("  %d %d %d %d\n", rst[0], rst[1], rst[2], rst[3]);
                printf("+ %d %d %d %d\n", rst[4], rst[5], rst[6], rst[1]);
                printf("--------------\n");
                printf("%d %d %d %d %d\n", rst[4], rst[5], rst[2], rst[1], rst[7]);
 
            }
        }
    }
    else
    {
        for (i = 0; i <= 9; i++)
        {
            if (ch[i] == 0)
            {
                rst[lv] = i;
                ch[i] = 1;
                DFS(lv + 1);
                ch[i] = 0;
            }
        }
    }
}
 
int main(void)
{
    DFS(0);
 
    return 0;
}

#. Other code

#include<stdio.h>
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 P(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;
                P(L+1);
                ch[i]=0;
            }
        }
    }
}
int main() {
    P(0);
 
    return 0;
}

line 4) 사용한 자연수를 담는 a[] 와 사용된 자연수를 체크하는 ch[] 

line 6~16) 

Send, More, Money 를 각 idx에 지정된 알파벳에 할당된 값으로 연산한 결과를 return

0	1	2	3	4	5	6	7
D	E	M	N	O	R	S	Y

line 18~38) level 을 늘려가면서 재귀함수를 호출

line 19~27) send()+more() 의 결과와 money() 의 결과가 같고, 

               s와 m이 0이 되면 안되므로 0이면 return,

               s와 m이 0이 아니라면 send, more, money 를 출력

line 28~37) 0부터 9까지의 수를 사용하여, 

               이미 사용된 자연수를 제외하고 각 알파벳에 자연수를 할당해본다.

#. Result

  - Output --------------------------------------------------------

   9 5 6 7

+ 1 0 8 5

-----------

1 0 6 5 2

------------------------------------------------------------------