[백준 1339] 단어 수학

[백준 1339] 단어 수학

문제 링크

#include <header.h>
using namespace std;
int N;
int ans = 0;
map<char, int> m;
vector<string> words;
int visit[11];
set<char> s;
vector<char> v;
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        words.push_back(str);
        for (int j = 0; j < str.length(); j++) {
            s.insert(str[j]);
        }
    }

    v.assign(s.begin(), s.end());
}

void calc() {

    int cnt = 0;
    for(int i=0; i<words.size(); i++){
        int n = 0;
        for(int j=0; j<words[i].length(); j++){
            n *= 10;
            n += m[words[i][j]];
        }
        cnt += n;
    }
    ans = max(ans, cnt);
}

void dfs(int cnt) {
    if(cnt > v.size()) return;
    if (cnt == v.size()) {
        calc();
    }
    for (int j = 9; j >= 0; j--) {
        if (!visit[j] && !m[v[cnt]]) {
            visit[j] = 1;
            m[v[cnt]] = j;
            dfs(cnt + 1);
            m[v[cnt]] = 0;
            visit[j] = 0;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    dfs(0);

    cout << ans << endl;
    return 0;
}

• 백트래킹 문제
• set으로 조합을 만들어야 하는 알파벳들만 구한다.
• dfs를 돌면서 알파벳마다 하나씩 숫자를 조합 해 본다.
• 모든 알파벳에 숫자를 할당했다면, calc를 통해 값을 구하고, 최댓값을 업데이트 해 준다.
• pow때문에 시간초과가 났다. pow 사용은 지양하도록 하자.