[Greedy] BOJ 1339 단어 수학

문제 링크 : www.acmicpc.net/problem/1339

1339번: 단어 수학

이 문제가 그리디 알고리즘으로 해결할 수 있다는 것을 캐치한다면,

일반적으로는 더 자릿수가 큰 수의 앞 자리 알파벳부터 큰 수를 부여하는 식의 접근을 할 것이다.

하지만 이러한 접근의 경우 각종 예외 케이스들을 관통하는 하나의 코드를 구현하기 매우 까다롭다.

 

예를 들어 ABC와 BB 9개, 총 10개의 단어에 대해

A = 9, B = 8, C = 7 이라면 987 + 88 * 9 = 1,779

A = 8, B = 9, C = 7 이라면 897 + 99 * 9 = 1,788 로,

더 긴 단어의 앞 자리 알파벳이 크다고 반드시 최댓값을 내지 않음을 알 수 있다.

 

이 문제를 백트래킹이 아닌 그리디 알고리즘으로 해결하기 위해서는 문제를 좀 더 간단화할 필요가 있다.

단어 ABCD는 1000A + 100B + 10C + D 로 나타낼 수 있으며,

각 단어들을 모두 위와 같이 나타내어 합하면 각 알파벳들을 미지수로 하는 하나의 식이 나온다.

이 식에서 계수가 가장 높은 순서대로 큰 수를 부여하면 문제를 해결할 수 있다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
 
using namespace std;
typedef pair<int, int> p;
 
int n;
vector<string> words;
vector<p> coef;
int curval = 9;
 
void get_coef(string s) {
    int exp = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        int letter = s[i] - 'A';
        coef[letter].first += pow(10, exp++);
    }
}
 
void init() {
    string input;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> input;
        words.push_back(input);
    }
 
    //총합의 계수와 알파벳을 저장
    for (int i = 0; i < 26; i++) coef.push_back({ 0, i });
}
 
bool cmp(p a, p b) {
    return a.first > b.first;
}
 
int main() {
    int result = 0;
    init();
 
    for (int i = 0; i < words.size(); i++) get_coef(words[i]);
 
    //계수를 내림차순으로 정렬
    sort(coef.begin(), coef.end(), cmp);
 
    for (int i = 0; i < coef.size(); i++) {
        result += coef[i].first * curval;
        curval--;
    }
 
    printf("%d\n", result);
 
    return 0;
}