1339: 단어 수학

• toc {:toc}

문제 확인하기

풀이

가장 최댓값을 만들기 위해서 각 알파벳마다 어떻게 1~9 사이의 숫자를 배정해줄 것인가에 대한 문제이다. 최댓값을 만드는데 가장 중점적인 부분은 자릿수이므로 해당 부분을 중점적으로 생각한다.

• 아이디어1
  • 자릿수(size)마다 가중치를 둬야한다고 생각했다.
  • 자릿수 제곱으로 알파벳마다 가중치를 주고 높은 알파벳부터 숫자 9에서 1까지 순차적으로 부여했다.
  • 문제 : 가중치 적용이 올바르지 않은 반례가 존재한다.
    • ex) 10, ABB, BC, BC, BC, BC, BC, BC, BC, BC, BC
    • A의 가중치 : 9, B의 가중치 : 41, C의 가중치 : 9
    • 최대가 아닌 값이 나온다.

#include <bits/stdc++.h>
using namespace std;
 
char alpha_num[30];
pair<char, int> alpha_scores[30];
 
bool compare(const pair<char, int>& a, const pair<char, int>& b){
    return a.second > b.second;
}
 
int main(){
    ios:: sync_with_stdio(false);
    cin.tie(0);
 
    vector<string> words;
 
    int N, res = 0;
    char num = '9';
    string str, temp;
 
    cin >> N;
 
    for(int i = 0; i < N; i++){
        cin >> str;
        int size = str.size()-1;
        words.push_back(str);
        for(int j = 0; j < str.size(); j++){
            alpha_scores[str[j]-'A'].first = str[j];
            alpha_scores[str[j]-'A'].second += (size+1)*(size+1);
            size--;
        }
    }
    sort(alpha_scores, alpha_scores+26, compare);
 
 
    for(int i = 0; i < 27; i++){
        if(alpha_scores[i].second == 0) continue;
        alpha_num[alpha_scores[i].first-'A'] = num--;
    }
 
    for(int i = 0; i < words.size(); i++){
        temp = "";
        for(int j = 0; j < words[i].size(); j++){
            temp += alpha_num[words[i][j]-'A'];
        }
        res += stoi(temp);
    }
 
 
    cout << res << '\n';
 
    return 0;
}

아이디어 1의 가중치를 사용하면 백의 자리와 일의 자리가 서로 같게 되기에 가중치 역할을 수행하지 못한다. 자릿수별로 가중치의 차이를 확실하게 둬야 한다.

• 아이디어 2
  • 생각해보니 가중치를 제곱 형태로 줄 필요가 없다. 그냥 자릿수대로 가중치를 주면 된다.
  • ex) 10, ABB, BC, BC, BC, BC, BC, BC, BC, BC, BC
    • 백의 자리는 100, 십의 자리는 10, 일의 자리는 1로 가중치를 적용한다.
    • 100A, 101B, 9C

#include <bits/stdc++.h>
using namespace std;
 
pair<char, int> alpha_scores[30];
 
bool compare(const pair<char, int>& a, const pair<char, int>& b){
    return a.second > b.second;
}
 
int main(){
    ios:: sync_with_stdio(false);
    cin.tie(0);
 
    vector<string> words;
 
    int N, res = 0;
    int num = 9;
    string str, temp;
 
    cin >> N;
 
    for(int i = 0; i < N; i++){
        cin >> str;
        int size = str.size()-1;
        words.push_back(str);
        for(int j = 0; j < str.size(); j++){
            alpha_scores[str[j]-'A'].first = str[j];
            alpha_scores[str[j]-'A'].second += pow(10, size--);
        }
    }
    sort(alpha_scores, alpha_scores+26, compare);
 
    for (int i = 0; i < 27; i++){
        if(alpha_scores[i].second == 0) continue;
        res += alpha_scores[i].second * num--;
    }
 
    cout << res << '\n';
 
    return 0;
}