[백준 1339] 단어수학 (C++)

1339번: 단어 수학

브루트 포스 - 순열 (연습)

 

7달 전에 그리디를 사용해서 풀었었는데 이번엔 백트래킹 완전탐색을 이용해서 풀었다.

 

 

모든 단어를 입력받고 단어에 사용된 알파벳(최대 10개)를 중복 없이 걸러내기 위해서 중복을 허용하지 않는 자료구조인 set을 사용했다.

 

10개의 알파벳에 9~0까지의 숫자를 매칭해주고 모두 매칭이 된 경우 (cnt == 알파벳의 개수)

최대 10개의 단어를 매핑테이블(table[27])을 이용해 모두 숫자로 바꾸고 각각을 더해주었다.

 

매칭은 table[27] 배열을 사용해서 특정 알파벳이 어떤 수와 연결되었는지 저장했다.

 

 

 

 

매핑테이블을 처음에 map<char, int> 를 사용해서 했더니 자꾸 시간초과가 발생했다.

그리고 dfs를 수행하는데 쓸데없는 정보들을 전역변수로 설정해주니 드디어 통과.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, LIM;
int res;
vector<string> words;
int table[27];
bool visited[10];
string alpha = "";
 
void input(){
    cin >> N;
    string str;
    for(int i = 0; i < N; i++){
        cin >> str;
        words.push_back(str);
    }
}
 
int word_to_int(string &word){
    int num = 0;
    for(int i = 0; i < word.size(); i++){
        num = num*10 + table[word[i] - 'A'];
    }
    
    return num;
}
 
void dfs(int cnt){
    if(cnt == LIM){
        // 주어진 모든 알파벳에 대해서 숫자를 부여했다면
        // 각 단어를 숫자로 변환 후 단어의 합을 구한다.
        int sum = 0;
        for(auto &w: words){
            sum += word_to_int(w);
        }
        res = max(res, sum);
        return;
    }
    
    for(int i = 9; i > 9-LIM; i--){
        if(visited[i]) continue;
        visited[i] = true;
        table[alpha[cnt] - 'A'] = i;
        
        dfs(cnt+1);
        
        visited[i] = false;
    }
}
 
void solve(){
    // ==알파벳 중복 제거==
    set<char> filter;
    
    for(auto &w: words){
        for(auto &c: w){
            filter.insert(c);
        }
    }
    
    
    for(auto &f: filter){
        alpha += f;
    }
    // ===============
    
    LIM = alpha.size();
    
    dfs(0);
    
    cout << res << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}