[백준 1339번] [그리디] 단어 수학

일단 이 문제를 보고 Greedy property를 발견하는 것은 그리 어렵지 않다.

 

직관적으로 생각해보면 제일 합이 크기 위해서는 자릿수가 제일 큰 것부터 봐가면서 해당하는 알파벳의 숫자를 키워나가면 되기 때문이다.

다만, 이렇게 접근할 경우에 상당히 복잡하다.

계속해서 어떤 알파벳이 처리 되었는지를 확인해주어야 하고(물론 방문 배열을 통해 처리할 수 있지만, 다른 문자열의 크기도 동시에 고려해야한다는 점에서 복잡하다.), 같은 자릿수의 알파벳의 경우도 어느 숫자를 배치해야할지 바로 결정하지 못하는 경우가 존재하기 때문이다.

 

예를 들어

ABC, CAB 문자열이 주어졌다고 가정하자.

그러면 Greedy property에 의해 A와 C가 9이거나 8일 때 가장 optimized하다.

다만, 첫번째 자리만 보고서는 각각 어느 것이 9이고 8인지 판단하지 못한다. 뒤까지 전부 고려했을 때 더 먼저 출현하는 것에 더 큰 수를 배치하는 것이 더 최적이기 때문이다.

즉, 이러한 성격때문에 단순히 방문배열로써 숫자를 매칭하는 것도 쉽지 않다.

 

이에 다른 방법을 조금 생각하게 되었다.

근본적으로 자릿수가 큰 것에 큰 숫자를 배치시키는 이유는 자릿수가 더 클 수록 pow(10, 자릿수 - 1 )과 곱한 값이 더 커지기 때문이다.

그러면 관점을 바꿔서 pow(10, 자릿수 - 1)을 dp에다가 따로 저장해둔 뒤, 나중에 해당 값이 큰 순서대로 숫자를 매칭시켜주면 된다.

즉, AAB를 100 * A + 10 * A + B로 보고 A * 110 + B로 간주하면 A는 110만큼, B는 1만큼이 할당되었으므로 A는 9, B는 8을 매칭시켜주면 된다.

 

추가적으로 ASCII attribute를 이용하면 26개의 배열만 관리해주면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    int n;
    cin >> n;
    vector<int> dp(26, 0);
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int i = 0; i < s.size(); i++){
            int current_value = s[i] - 'A';
            dp[current_value] += pow(10, s.size() - i - 1);
        }
    }
    sort(dp.begin(), dp.end(), greater<int>());
    int result = 0;
    int index = 9;
    for(int i = 0; i < 10; i++){
        result += dp[i] * index;
        if(index > 0) index--;
    }

    cout << result << "\n";
    return 0;
}