(C++) - 백준(BOJ) 15811번 : 복면산?!

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

15811번: 복면산?!

brute force 문제였습니다.

 

 

 

📕 풀이방법

 1. 입력을 받고 나온 알파벳 종류의 개수를 세봅니다. 

 

 

 2. 숫자로 표현하려면 나오는 알파벳의 종류가 10개 이하여야 합니다. 그보다 초과하는 종류에 대해서는 서로 다른 한 자리 수의 번호를 매길 수 없기 때문입니다. 따라서 초과한다면 NO를 출력하고 종료합니다.

 

 3. 나온 알파벳들을 겹치지 않도록 저장합니다. 이 후 각 알파벳에 대해 겹치지 않도록 0 ~ 9의 숫자를 배분합니다.

 

 4. 배분 이후 답이라면 flag를 세워줍니다.

 

 5. 모두 확인해서 하나라도 답이 있다면(flag가 1이라면) YES 아니라면 NO를 출력합니다.

---

 

 

📕 Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string words[3], usedAlpha;
int alpha[26], ck[11], flag;
vector <int> digit;

void dfs(int depth){
    if(depth == usedAlpha.size()){
        ll nums[3] = {0};
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < words[i].size(); j++){
                nums[i] *= 10;
                nums[i] += alpha[words[i][j] - 'A'];
            }
        }

        if(nums[0] + nums[1] == nums[2]) flag = 1; 
        return;
    }

    int cur = usedAlpha[depth] - 'A';
    for(int i = 0; i < 10; i++){
        if(ck[i]) continue;
        ck[i] = 1;
        alpha[cur] = i;
        dfs(depth + 1);
        ck[i] = 0;
        alpha[cur]--;
    }
}

int main(){
    cin >> words[0] >> words[1] >> words[2];
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < words[i].size(); j++)
            alpha[words[i][j] - 'A'] = 1;

    int cnt = 0;
    for(int i = 0; i < 26; i++)
        if(alpha[i]) usedAlpha += i + 'A',cnt++;

    if(cnt > 10){ cout << "NO"; return 0; } 

    memset(alpha,0,sizeof(alpha));
    dfs(0);        
    if(!flag) cout << "NO\n";
    else cout << "YES\n";
}