[Algorithm] Baekjoon 1339번 : 단어 수학

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

1339번: 단어 수학

bool cmp(const vector<int>& a, const vector<int>& b)
{
    return a[0] > b[0];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    vector<string> v;
    vector<vector<int>> mv(26, vector<int>(2));
    map<char, int> m;
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        string temp;
        cin >> temp;
        v.push_back(temp);
    }
    
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v[i].size(); j++)
        {
            mv[v[i][j] % 65][0] += pow(10, v[i].size() - j - 1);
            mv[v[i][j] % 65][1] = v[i][j] % 65;
        }
    }
 
    sort(mv.begin(), mv.end(), cmp);
 
    for (int i = 0; i < mv.size(); i++)
    {
        if (mv[i][0] == 0) break;
 
        m[mv[i][1] + 65] = 10 - i - 1;
    }
 
    int sum = 0;
 
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v[i].size(); j++)
        {
            int temp = pow(10, v[i].size() - j - 1);
            temp *= m[v[i][j]];
            sum += temp;
        }
    }
 
    cout << sum;
}

 

알파벳문자열이 주어졌을 때 어떤 순서로 알파벳에 숫자를 매핑해야 최대값이 나오는가를 알아야 하는 문제.

백트래킹 문제 추천에 있길래 백트래킹으로만 접근하려다가 뭔가 수학적인 방법이 있을 것 같아서 따로 검색해봤다.

각 자리수의 합으로 내림차순을 하면 된다는 내용만 알고 바로 코드로 짰더니 통과했다.