[BOJ][C++] 백준 15811번: 복면산?!

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를 한 줄에 출력한다.

 

풀이

수가 18자리까지 될 수 있다 -> int가 아닌 long long으로 해야한다는 사실을 주의하자

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

string input[3];
vector<char> usedAlpha;
int alphabet[26];
bool numUsed[11], ans=false;

void recur(int cnt) {
    if(ans) // 이미 구해졌다면 패스
        return;
    
    if(cnt == usedAlpha.size()) { // 할당 다 했니?
        // wordNum[x] = x번째 입력값(문자열)을 수로 변환한거
        long long wordNum[3];
        wordNum[0] = wordNum[1] = wordNum[2] = 0;
        for(int i=0; i<3; i++) {
            for(int j=0; j<input[i].size(); j++) {
                wordNum[i] *= 10;
                wordNum[i] += alphabet[input[i][j]-'A'];
            }
        }
        
        // 변환한거 계산 맞니?
        if(wordNum[0] + wordNum[1] == wordNum[2])
            ans = true;
        
        return;
    }
    
    int cur = usedAlpha[cnt]-'A'; // 현재 대응시켜볼 알파벳
    for(int i=0; i<=9; i++) {
        if(numUsed[i]) // 이미 사용한 숫자라면 패스
            continue;
        
        // 숫자 사용, 알파벳에 숫자 할당, 재귀(백트래킹)
        numUsed[i] = true;
        alphabet[cur] = i;
        recur(cnt+1);
        alphabet[cur] = i-1;
        numUsed[i] = false;
    }
    
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> input[0] >> input[1] >> input[2];
    for(int i=0; i<3; i++)
        for(int j=0; j<input[i].size(); j++)
            alphabet[input[i][j] - 'A'] = 1;
    
    for(int i=0; i<26; i++)
        if(alphabet[i]) // 사용된 알파벳이라면
            usedAlpha.push_back(i+'A');
    
    // 사용된 글자가 10개를 넘어버린다면
    if(usedAlpha.size() > 10) {
        cout << "NO";
        return 0;
    }
    
    recur(0);
    
    if(ans)
        cout << "YES";
    else
        cout << "NO";
    
    return 0;
}

/*
 */