[Baekjoon,1339] 단어 수학

백트래킹을 하며 모든 경우의 수를 탐색할 수 있다. 탐색 하며 더 큰 값이 나오면 계속해서 갱신해 나가는 것이다. 하지만 이보다 더욱 간단한 방법이 있다. 바로 그리디한 수학적 방법이다.

그 방법은 다음과 같다. 제일 자릿수가 큰 숫자부터 9를 매칭해 나아가며 자릿수가 같다면 더 많이 출현하는 숫자에 높은 수를 매칭하는 것이다. 예를 들어 설명하기 위해 백준에서 주어진 두 번째 예제를 보자.

2
GCF
ACDEB

여기서 각 문자를 숫자로 생각하여 수식으로 표현하면 아래와 같다.

• $ GCF = 100 \times G + 10 \times C + 1 \times F $
• $ ACDEB = 10000 \times A + 1000 \times C + 100 \times D + 10 \times E + 1 \times B $

이 자릿수에 위치한 값들을 알파벳 별로 합하면 아래와 같다.

$ cost[A]=10000 \\
cost[B]=1 \\
cost[C]=1010 \\
cost[D]=100 \\
cost[E]=10 \\
cost[F]=1 \\
cost[G]=100 $

이를 오름차순으로 정렬하면 아래처럼 된다.

$ cost[B]=1 \\
cost[F]=1 \\
cost[E]=10 \\
cost[D]=100 \\
cost[G]=100 \\
cost[C]=1010 \\
cost[A]=10000 $

여기서 제일 큰 합을 가진 $A$부터 9를 매칭하고 차례로 $C$는 8, $G$는 7을 매칭해 나아간다. 결국 이를 계산하면 $99437$이라는 결과가 나온다.

구현

위와 같은 과정을 코드로 구현하면 아래와 같다.

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int n;
vector<string> s;
int cost[26];

void caclCost()
{
    memset(cost,0,sizeof(cost));
    for(int i=0;i<n;++i)
    {
        int len=s[i].size();
        for(int k=0;k<len;++k)
        {
            int idx=len-k-1;
            cost[(s[i][idx]-'A')]+=pow(10,k);
        }
    }
    sort(cost,cost+26);
}

int main()
{
    cin>>n;
    s=vector<string>(n);
    for(int i=0;i<n;++i)
        cin>>s[i];
    
    caclCost();
    
    int ret=0, counter=9;
    for(int i=25;i>=0;--i)
    {
        if(cost[i]==0)
            break;
        ret+=cost[i]*counter--;
    }
    cout<<ret<<endl;
    
    return 0;
}