BOJ - 복면산?! (15811)

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

15811번: 복면산?!

 

오늘도 완전탐색입니다.

세 개의 문자열이 주어지면, 존재하는 각 알파벳에 

0부터 9까지의 숫자를 분배해주고, 덧셈을 만족하는지 보면 됩니다.

 

여기서 요점은 바로 0부터 9까지 숫자를 분배해주는 것을 구현하는 것입니다.

 

#include <bits/stdc++.h>
 
using  namespace std;
 
bool chk[11];    // 0~9까지의 숫자를 분배했는지 여부를 체크하기 위한 배열
vector<int> v;    // 등장하는 중복 제거한 알파벳 값을 가지고 있는 배열
int asg[33];    // 각 알파벳에 0~9 사이의 어떤 값을 할당했는지 저장하고 있는 배열
string s[3];    // input으로 들어오는 값을 저장하는 문자열
 
void sol(int cur){            
    if(cur == v.size()){        // 등장하는 모든 알파벳에 값을 할당했으면 맞게 할당했는지 확인해본다.
        ll b[3] = {};            // 각 값을 숫자로 변환하여 저장하기 위한 변수
        for(int i = 0; i < 3; i++){            // 알파벳 숫자를 진짜 숫자로 변환하는 과정
            for(int j = 0; j < s[i].size(); j++){
                b[i] *= 10;
                b[i] += asg[s[i][j] - 'A'];
            }
        }
 
        if(b[0] + b[1] == b[2]) {    // 맞는지 확인
            cout << "YES";
            exit(0);
        }
        return;
    }
 
    int idx = v[cur];                // 알파벳 
 
    for(int i = 0; i <= 9; i++){    // 0~9 숫자 할당을 시도해본다
        if(chk[i]) continue;        // 이미 할당했다면, 무시하고 다른 숫자를 할당해본다
        asg[idx] = i;                // 숫자를 할당한다
        chk[i] = true;                // 숫자가 할당됐음을 기록한다.
        sol(cur + 1);                // 다음 알파벳에 할당을 시도한다
        chk[i] = false;                // 숫자 할당을 취소한다
        asg[idx] = -1;
    }
}
 
int main(){
    bool chk[30] = {};
    for(int i = 0; i < 3; i++){
        cin >> s[i];
        for(int j = 0; j < s[i].size(); j++)
            chk[s[i][j] - 'A'] = true;
    }
 
    for(char a = 'a'; a <= 'z'; a++){
        if(chk[a - 'a']) v.push_back(a - 'a');
    }
 
    if(v.size() <= 10) {    // 10개 이하 알파벳이 등장할 때만 숫자 할당을 시도한다
        sol(0);
    }
    
    cout << "NO";
}