복면산?! - 15811

//15811 - 복면산?!
 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
 
string s1, s2, s3;
map<char, int> M;
vector<bool> exist;
string bucket;
vector<int> toNum;
vector<bool> used;
 
bool cal()
{
    int a = 0, b = 0, c = 0;
    int mul = 1;
    for(int i = s1.size()-1; i>=0; --i)
    {
        a += toNum[M[s1[i]]]*mul;
        mul *= 10;
    }
    mul = 1;
    for(int i = s2.size()-1; i>=0; --i)
    {
        b += toNum[M[s2[i]]]*mul;
        mul *= 10;
    }
    mul = 1;
    for(int i = s3.size()-1; i>=0; --i)
    {
        c += toNum[M[s3[i]]]*mul;
        mul *= 10;
    }
    if(a+b == c)
        return true;
    return false;
}
 
bool assign(int idx, int num)
{
    used[num] = true;
    toNum[idx] = num;
    if(idx == bucket.size()-1)
    {
        used[num] = false;
        return cal();
    }
    for(int i = 0; i<10; ++i)
        if(!used[i])
            if(assign(idx+1, i))
                return true;
    used[num] = false;
    return false;
}
 
int main()
{  
    bucket = "";
    exist = vector<bool>(26, false);
    cin >> s1 >> s2 >> s3;
    for(int i = 0; i<s1.size(); ++i)
        if(!exist[s1[i] - 'A'])
            exist[s1[i] - 'A'] = true, bucket += s1[i];
    
    for(int i = 0; i<s2.size(); ++i)
        if(!exist[s2[i] - 'A'])
            exist[s2[i] - 'A'] = true, bucket += s2[i];
 
    for(int i = 0; i<s3.size(); ++i)
        if(!exist[s3[i] - 'A'])
            exist[s3[i] - 'A'] = true, bucket += s3[i];
    
    if(bucket.size() > 10)
    {
        cout << "NO" << "\n";
        return 0;
    }
 
    sort(bucket.begin(), bucket.end());
    for(int i = 0; i<bucket.size(); ++i)
        M[bucket[i]] = i;
    
    toNum = vector<int>(bucket.size());
    used = vector<bool>(10, false);
 
    for(int i = 0; i<10; ++i)
        if(assign(0, i))
        {
            cout << "YES";
            return 0;
        }
    cout << "NO";
}

 

 

 

 

 

 

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

15811번: 복면산?!

 

 

 

 

 

 

복면산?!

최대 알파벳의 개수는 10개, 각각의 알파벳에 0-9의 숫자를 매칭하는 방법은 10! 입니다.

완전탐색을 사용할만한 입력이므로 input으로 들어오는 알파벳을 골라내 0-9의 숫자를 매칭해 

a+b == c인지 아닌지 확인해 정답을 구했습니다.