[BOJ] 백준 1339번: 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

---

문제 설명

N개의 알파벳 대문자로만 이루어진 단어가 주어지고, 각 단어의 알파벳을 0~9의 숫자 중 하나의 수로 바꿔서 N개의 수를 합하는 문제입니다.

GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 된다고 합니다.

---

문제 풀이

각 알파벳에 1을 대입하여 알파벳 별 합을 구해봅니다.

만약 ABC, BBA 두가지 단어가 주어진다면 A의 합은 100 + 1 로 101이 되고, B의 합은 10 + 110 = 120, C의 합은 1로 볼 수 있습니다.

이 때, 더한 합이 큰 순서대로 9부터 차례대로 수를 대입하면 최대값을 구할 수 있습니다. (탐욕법) 

B = 120 * 9 = 1080, A = 101 * 8 = 808 , C = 7로 A = 8 , B = 9, C = 7 을 대입했을때 897 + 889 = 1786으로 단어의 합의 최댓값을 구할 수 있습니다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
int cmp(long long a, long long b) {
	return a > b;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	long long sum[26] = { 0, };
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		int len = str.length();
		long long decimal = 1;
		for (int j = len -1; j > -1; j--) {
			sum[str[j] - 'A'] += decimal;
			decimal *= 10;
		}
	}
	vector<long long> v;
	for (int i = 0; i < 26; i++) {
		if (sum[i]) {
			v.push_back(sum[i]);
		}
	}
	sort(v.begin(), v.end(), cmp);
	long long ans = 0;
	int d = 9;
	for (auto ch : v) {
		ans += (ch * d);
		d--;
	}
	cout << ans;
}