백준 1339번 - 단어 수학

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

문제의 분류는 백트래킹으로 되어 있는데 간단한 수학적 사고(?)를 통해서 문제를 풀었다.

각각의 알파벳에 자리수가 있기 때문에 우선순위가 존재한다.

예를들어, ABC가 있을 때 A=100, B=10, C=1로 치환해서 문제를 풀면 된다.

모두 대문자만 입력이 주어지기 때문에 총 26개의 값이 들어올 수 있으며

자리수에 해당하는 값으로 치환해서 각각의 알파벳에 값을 넣어주면 된다.

다음으로 알파벳에 값을 큰 순서대로 소팅한 후에, 큰 값부터 9,8,7을 곱해주는 식으로 모든 값을 더해주면 된다.

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(){
    
    int N;
    cin>>N;
    
    //'A'=65
    int alphabet[26]={0};
    string s;
    for(int i=0;i<N;i++){
        cin>>s;
        for(int j=0;j<s.length();j++){
            alphabet[s[j]-65]+=(int)pow(10,s.length()-j-1);
        }
    }
    
    int ans=0;
    vector<int> vec; //존재하는 알파벳 담는 배열
    for(int i=0;i<26;i++){
        if(alphabet[i]){
            vec.push_back(alphabet[i]);
        }
    }
    
    int cnt=9;
    sort(vec.begin(),vec.end(),greater<int>()); //내림차순 정렬
    for(int i=0;i<vec.size();i++){
        ans+=vec[i]*(cnt--);
    }
    cout<<ans<<endl;
    return 0;
}