[Gold 4] 1339 단어 수학

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

1339번: 단어 수학

 

이 문제는 그리디 알고리즘을 사용해서 해결할 수 있다.

 

알파벳으로만 이루어진 숫자의 합이 최대가 되도록 하는 방법은 다음과 같다.

가장 높은 자릿수부터 9를 순차적으로 부여하면 합이 최대가 된다.

이때 같은 문자는 같은 값이 되어야하며, 같은 값인 문자는 존재하지 않게 해야한다.

 

처음 문제를 해결할 때 자릿수를 배열에 담아 배열을 정렬한 후 순차적으로 9부터 값을 부여하였다.

이러한 방법은 아래의 경우는 해결할 수 없는 문제가 있다.

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

이 경우는 B = 9, A = 8인 경우 값이 최대가 된다. 즉, 1790이 답이 되어야한다.

 

문제의 의도대로 답을 구하기 위해서는 자릿수에 나온 알파벳의 합을 배열에 담아 가장 큰 수대로 숫자를 부여하는 방법을 사용해야한다.

쉽게 설명하면 위 경우 (100 * A + 10 * B + 1 * B) + 9 * (10 * B + 1 * B) = 100 * A + 110 * B이므로 

B에 9를 부여하고 A에 8을 부여하면 990 + 800 = 1790이 된다.

 

예제에 이 공식을 사용하여 해결한다면

(100 * G + 10 * C + 1 * F) + (10000 * A + 1000 * C + 100 * D + 10 * E + 1 * B) 

= 10000 * A + 1010 * C + 100 * G + 100 * D + 10 * E + 10 * F + 1 * B가 된다.

즉, A = 9, C = 8, G = 7, D = 6, E = 5, F = 4, B = 3이 된다.

 

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;

int N;
int value = 0;
vector<pair<char,int>> arr;
vector<string> voc;
map<char, int> m;
map<char,int, greater<int>> alpha;

bool bigger(pair<char, int>& a, pair<char, int>& b) {
	return a.second > b.second;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	string input;
	
	for (int i = 0; i < N; i++) {
		cin >> input;
		int len = input.length();
		voc.push_back(input);
		for (int j = 0; j < len; j++)
			alpha[input[j]] += pow(10, len - j);
	}
	for (auto iter = alpha.begin(); iter != alpha.end(); iter++) {
		arr.push_back({ iter->first,iter->second });
	}
	sort(arr.begin(), arr.end(), bigger);
		
	int number = 9;
	for (int i = 0; i < arr.size(); i++) {
		m[arr[i].first] = number--;
	}
	
	for (int i = 0; i < voc.size(); i++) {
		string target = voc[i];
		int len = target.length();
		string number = "";
		for (int j = 0; j < len; j++) {
			int calc = m[target[j]];
			number += to_string(calc);
		}
		value += stoi(number);
	}
	
	cout << value << '\n';
}