C++ 백준 1339 (단어 수학)

백준 1339 (단어 수학)

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

1339번: 단어 수학

---

설명

---

간단한 정렬로 풀 수 있는 문제였다.

 

각 자리수에 대해 가중치를 두고 그 가중치를 정렬한 뒤에 가중치가 높은 알파벳부터 9~1까지 차례대로 주면 된다.

 

예시를 살펴보자

 

ABB

CAD

 

라는 두 수를 합친다고 가정해보자. 

그러면 (100+10)*A + (10+1)*B + 100*C + D 가 될 것인데, 수가 가장 크려면 자신앞에 붙은 상수값이 가장 큰 알파벳에게 되도록 큰 숫자를 주면 될 것이다.

(아마 되도록 큰 숫자를 준다는 의미에서 이 문제가 그리디 알고리즘으로 분류되는 것 같다)

 

그러다면 A=9, C=8, B=7, D=6을 주어 답은 990+800+77+6 = 1873이 될 것이다.

 

문제에서 주어지는 문자열의 개수는 10개 이하이고, 각 자리수의 최대는 8자리이 때문에 최악의 경우

 

AAAAAAAAAA 이라는 문자열이 10개 들어온다면 가중치의 합은

111111111111*10이 될것이다. 약 1억 1천만정도 이기 때문에 int형으로 충분히 받을 수 있다.

 

또한 실제 합을 구할 때도 위 상황에서 A에는 9가 들어가도 (10억-1)이 답이기 때문에 최종 답 또한 int형으로 충분히 받을 수 있다.

 

만약 각 문자열의 최대길이가 10이 넘어가서 가중치를 long long으로도 받을 수 없을 때는 백트래킹을 이용하면 될 것 같다.

 

즉, 정리하자면 각 알파벳에 대한 가중치를 구한 후 가중치 순으로 정렬하여 가장 큰 가중치를 갖는 알파벳에게 가능 한 큰 숫자를 주면 된다!

 

구현

---

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

vector <pair<int, char>> v;
int tmp[26];
int p[10];
int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
    int ans=0;
    string str;
    p[0]=1;
    for(int i=1;i<10;i++){
        p[i] = p[i-1]*10;
    }
    cin>>n;
    memset(tmp, 0, sizeof(tmp));
    for(int i=0;i<n;i++){
        cin>>str;
        int k=0;
        for(int j=str.length()-1;j>=0;j--){
            tmp[str[j]-'A']+=p[k];   
            k++;
        }
    }
    for(int i=0;i<26;i++){
        if(tmp[i]>0) v.push_back({tmp[i],i+'A'});
    }
    sort(v.begin(),v.end(),greater<>());
    int m=9;
    for(int i=0;i<v.size();i++){
        ans+=m*v[i].first;
        m--;
    }
    cout<<ans;
    return 0;
}