Baekjoon 1339번 단어 수학

문제

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

걸린 시간

01 : 50 : 28 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
typedef long long ll;
using namespace std;

int n;
vector<pair<int, char>> digit(26);
map<char, int> change;
vector<string> word;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    string s;
    for(int i = 0; i < n; i++){
        cin >> s;
        word.push_back(s);
        for(int j = 0; j < s.size(); j++){
            int upper = (int)s[j]-0x41;
            digit[upper].first -= pow(10, s.size()-j-1);
            digit[upper].second = s[j];
        }
    }
    sort(digit.begin(), digit.end());
    int count = 9;
    for(int i = 0; i < digit.size(); i++){
        if(count >= 0){
            change[digit[i].second] = count;
            count--;
        }
    }
    ll ans = 0;
    for(int i = 0; i < word.size(); i++){
        string tmp;
        for(int j = 0; j < word[i].size(); j++)
            tmp += to_string(change[word[i][j]]);
        ans += atoll(tmp.c_str());
    }
    cout << ans;
    return 0;
}

완전 탐색으로 어떻게 구현해야될 지 감이 오질 않아서 그리디로 접근했다.

알파벳들의 합이 최대가 되도록 하려면 제일 높은 자리수를 가지는 알파벳이 큰 수를 갖게끔 해야하는건 당연하다. 그 다음으로 생각해야하는 것이 같은 자리수를 가지는 서로 다른 알파벳의 우선순위를 정하는 것인데 이 부분에서 올바른 방법을 떠올려내지 못했다. 출현횟수를 세는 방법을 이용했었는데 조금만 생각해봐도 반례를 떠올릴 수 있는 틀린 방법이다. 하지만 다른 방법이 떠오르지 않아 이대로 진행했고 오답을 받은 후 결국 답을 보게 되었다.

올바른 방법은 각 알파벳이 출현한 자리수의 값을 누적시켜 값이 제일 큰 순서대로 숫자를 부여하는 것이였다.