[C++] 백준/Gold/1339. 단어 수학

문제: 단어 수학(백준 1339번)

문제 분석

주어진 여러 단어에서 각 알파벳에 0부터 9까지의 숫자를 배정하여, 이 단어들이 나타내는 수들의 합을 최대화하는 문제이다.
즉, 각 알파벳에 적절한 가중치를 부여해, 전체 합이 최대가 되는 배정을 찾아야 한다.

---

알파벳 집합 생성

• 입력받은 각 단어를 벡터 v에 저장하고, 각 단어에 포함된 알파벳을 unordered_map<char, int> dict에 넣어 초기값 0으로 설정한다.

Calc 함수

• Calc 함수는 현재 dict의 배정 상태를 기반으로, 각 단어의 값을 계산해 전체 합을 구한다.
• 각 단어의 문자들을 해당 알파벳에 할당된 숫자로 바꾼 후 stoi를 통해 정수로 변환하고, 이를 모두 합산한다.

BT 함수 (백트래킹)

• BT(int depth) 함수는 아직 숫자가 배정되지 않은 알파벳에 대해, 가능한 숫자 (9부터 차례대로)를 할당하면서 Calc 함수를 호출하여 최대 합을 찾는다.
• 만약 depth가 dict.size()와 같아지면, 모든 알파벳에 배정이 완료된 것이므로 현재 계산된 합을 출력한다.
• 아직 할당되지 않은 알파벳들에 대해 임시로 숫자 9 - depth를 배정한 후 Calc() 결과를 비교하고, 가장 큰 합을 주는 알파벳을 선택하여 확정한 후 재귀적으로 다음 단계로 넘어간다.

main 함수

• 테스트 케이스에서 단어의 개수를 입력받고, 각 단어를 v 벡터에 저장한다.
• 각 단어에 등장하는 알파벳을 dict에 삽입하여, 중복 없이 관리한다.
• 마지막으로 BT(0)를 호출하여 백트래킹을 시작한다.

코드 전체

#include <bits/stdc++.h>
using namespace std;

unordered_map<char, int> dict;
vector<string> v;

int Calc() {
    int sum = 0;
    for (string s : v) {
        for (char &c : s) {
            c = dict[c] + '0';
        }
        sum += stoi(s);
    }
    return sum;
}

void BT(int depth) {
    if (depth == dict.size()) {
        cout << Calc();
        return;
    }
    
    int maxVal = 0;
    char c = ' ';
    for (auto &i : dict) {
        if (i.second != 0) continue;
        i.second = 9 - depth;
        if (maxVal < Calc()) {
            maxVal = Calc();
            c = i.first;
        }
        i.second = 0;
    }
    dict[c] = 9 - depth;
    BT(depth + 1);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        v[i] = s;
        for (const char& c : s) {
            dict[c] = 0;
        }
    }
    BT(0);
}