[BOJ/Gold 4] 백준 15811 복면산?!(C++)

문제 링크

https://www.acmicpc.net/problem/15811

15811번: 복면산?!

 

 

문제

복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다.

대표적으로 SEND+MORE=MONEY가 있다.

  SEND
+ MORE
------
 MONEY

S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2로 바꾸면 식이 성립한다.

  9567
+ 1085
------
 10652

복면산 문제가 주어질 때, 답이 존재하는지 여부를 출력하시오.

단, 같은 문자는 같은 숫자에 대응되어야 하며, 서로 다른 문자는 서로 다른 숫자를 나타낸다. 또한, 수는 0으로 시작할 수 있다.

입력

세 단어가 공백을 두고 주어진다. 첫 번째 단어와 두 번째 단어를 더한 결과가 세 번째 단어임을 의미한다.

단어는 공백 없이 알파벳 대문자로만 이루어져 있으며 각 단어의 길이는 18자리를 넘지 않는다.

출력

계산식에 해답이 존재한다면 YES를, 그렇지 않다면 NO를 한 줄에 출력한다.

예제 입력 1

SUN FUN SWIM

예제 출력 1

YES

예제 입력 2

P P AP

예제 출력 2

NO

힌트

예제 입력 1은 067+867=0934와 167+867=1034를 포함하여 49개의 해답이 존재한다.

알고리즘 분류

• 백트래킹

풀이

알파벳의 개수는 26개지만, 한 자리 숫자는 최대 10개가 존재한다. 따라서 최악의 경우 10!가지의 경우의 수가 존재한다. 

식에서 존재하는 알파벳의 개수를 구하고 해싱을 통해 순번을 매긴다. 그리고 DFS를 통해 알파벳에 번호를 부여한다.

숫자를 부여한 후 계산했을 때 식이 성립된다면 바로 YES를 출력하고 실행을 종료한다.

그런 경우가 없다면 NO를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 26
#define INF 1e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
string Init[3];
vector<int> Alpha;
int Checked[MAX];
bool visited[MAX];
int Number[MAX];
int Index = 0;

void input() {
    for (int i = 0; i < 3; i++) {
        cin >> Init[i];
        for (int j = 0; j < Init[i].size(); j++) {
            Checked[Init[i][j] - 'A'] = true;
        }
    }
}

void DFS(int Depth) {
    if (Depth == Alpha.size()) {
        LL Tmp[3] = { 0,0,0 };
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < Init[i].size(); j++) {
                LL Cur = Number[Init[i][j] - 'A'];
                Tmp[i] *= 10;
                Tmp[i] += Cur;
            }
        }
        if (Tmp[0] + Tmp[1] == Tmp[2]) {
            cout << "YES\n";
            exit(0);
        }
        return;
    }
    else {
        int Now = Alpha[Depth];
        for (int i = 0; i < 10; i++) {
            if (!visited[i]) {
                visited[i] = true;
                Number[Now] = i;
                DFS(Depth + 1);
                Number[Now] = -1;
                visited[i] = false;
            }
        }
    }
}

void settings() {
    for (int i = 0; i < MAX; i++) {
        if (Checked[i]) {
            Alpha.push_back(i);
        }
    }
    if (Alpha.size() <= 10) {
        DFS(0);
    }
}

void find_Answer() {
    cout << "NO\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}