[ 백준 BOJ ] 1132번 - 합 (C++)

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

 

생각 흐름

• 각 알파벳에 0~9의 수를 대입해주면 간단하게 풀릴 거라 생각했다. 이에 따른 시간 복잡도도 10!으로 3600만이므로 2초안에 넉넉했다.
• 이제 맨 앞자리에는 0이 올 수 없으므로 시간 개선을 위해 이에 대해 처리도 해주었다.

#include <iostream>
#include <memory.h>
#include <vector>

using namespace std;

int N;
vector<string> v;
bool nonZero[10];
int alpha[10];
bool checked[10];

long long answer = 0;

long long cal(){
    long long ans = 0;
    for(int i = 0; i<v.size(); i++){
        long long tmp = 0;
        for(int j = 0; j<v[i].size(); j++){
            tmp*=10;
            tmp+=alpha[v[i][j]-'A'];
        }
        ans+=tmp;
    }
    
    return ans;
}

void dfs(int depth){
    if(depth==10){
        answer = max(answer, cal());
        return;
    }
    
    for(int i = 0; i<10; i++){
        if(i==0 && nonZero[depth]) continue;
        if(checked[i]) continue;
        
        checked[i]=true;
        alpha[depth]=i;
        dfs(depth+1);
        checked[i]=false;
        alpha[depth]=0;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
   
    cin>>N;
    
    for(int i = 0; i<N; i++){
        string tmp;
        cin>>tmp;
        
        v.push_back(tmp);
        nonZero[tmp[0]-'A']=true;
    }
    
    dfs(0);
    
    cout<<answer<<endl;
    
    return 0;
}