[BOJ 1339] 단어 수학

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

1339번: 단어 수학

 

문제는 알파벳이 들어왔을 때 각 알파벳마다 0부터 9까지 숫자 중 하나로 바꿨을 때의 합의 최댓값을 구하는 문제입니다.

 

일단 경우의 수는 10! 가지이기 때문에 시간 초과가 발생하지 않지만 각 경우마다 합을 구하는 로직이 들어가기 때문에 그렇게 하면 시간 초과가 발생하게 됩니다. 

 

그래서 다른 방법을 생각해봤는데 문제를 잘 보시면 제일 앞 자릿수에 큰 수를 할당하면 문제를 풀 수 있습니다. 예를 들어 ABC 라고 되어 있으면 A가 제일 앞 자릿수(큰 자리)이기 때문에 A에 9를 할당하고 B에 8, C에 7 이렇게 할당을 하면 제일 큰 자릿수를 만들 수 있습니다.

 

이러한 방식(그리디)으로 문제를 풀 수 있습니다.

 

예제 1번은 AAA, AAA이기 때문에 A의 자릿수는 100+10+1+100+10+1= 222입니다. 여기에 제일 큰 9를 할당해주면 답은 222*9 = 1998이 됩니다

 

예제 2번은 GCF, ACDEB 이고 A는 10000, B는 1, C는 10+1000=1010, D는 100, E는 10, F는 1, G는 100 입니다. 알파벳을 자릿수에 따라 정렬을 하면, A, C, D, G, E, B, F 입니다. 같은 자릿수에 대해선 어떤 것이 먼저 오든 상관없습니다. 그럼 이 순서대로 값을 할당하면 정답을 구할 수 있습니다. A(10000*9)+C(1010*8)+D(100*7)+G(100*6)+E(10*5)+B(1*4)+F(1*3) = 99437

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <array>
#include <math.h>
#include <stack>
#include <map>
#include <string.h>
#include <set>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N = 0;
	cin >> N;

	vector<string> arr(N);
	vector<int> w(26, 0);
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];	

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < arr[i].size(); j++)
		{
			w[arr[i][j] - 'A'] += pow(10, arr[i].length() - j - 1);
		}
	}

	priority_queue<int> pq;

	for (int i = 0; i < 26; i++)
	{
		pq.push(w[i]);
	}

	auto answer = 0;

	for (int i = 9; i >= 0; i--)
	{
		int top = pq.top();
		pq.pop();

		answer += top * i;
	}

	cout << answer;

	return 0;
}