백준 1339 : 단어 수학

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

1. 접근

• 처음에는 단순하게 가장 자릿수가 높은 곳부터 큰수를 넣어주면 된다고 생각했으나, 반례로 인해 오답이 되었다.
• 결국 브루트포스로 next_permutation 순열 함수를 사용해서 최대 10! 의 계산을 해주게되었다
• 그리디로 푸는 경우, 각 문자로 계산할 수 있는 가장 큰 값을 표현해서 그때의 최댓값을 구하면 된다고 한다.
  (https://yabmoons.tistory.com/132)

※ next_permutation은 내림차순으로 순열을 만드므로, sort로 미리 정렬해주는 것을 잊지말자

2. 반례

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

정답 : 1790

3. 나의 풀이

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

int main() {
	int n;
	cin >> n;

	vector<string> words;
	vector<char> word;
	map<char, int> match;

	int num = 9;
	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;
		words.push_back(input);
		for (int j = 0; j < input.length(); j++) {
			if (find(word.begin(), word.end(), input[j]) == word.end()) {
				word.push_back(input[j]);
			}
		}
	}
	sort(word.begin(), word.end());

	int ret = 0;
	do {
		for (int i=0; i <word.size(); i++) {
			if (word[i] != NULL)	match[word[i]] = i+(10-word.size());
			else match[word[i]] = 0;
		}
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int tem = 0;
			for (int j = 0; j < words[i].length(); j++) {
				tem = tem * 10 + match[words[i][j]];
			}
			sum += tem;
		}
		ret = max(ret, sum);
	} while (next_permutation(word.begin(), word.end()));

	cout << ret << "\n";

	return 0;
}