백준 1339 단어수학

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

1339번: 단어 수학

 

본문제는 N개의 단어(최대 10개) 의 합을 단어를 구성하는 알파벳을 어떤숫자로 매칭하였을 때 최대값이 되는지 구해야 하는 문제이다. 그런데 나열된 알파벳의 총 가지수가 10개를 넘어가지않고 두개이상의 알파벳이 같은 숫자와 매핑되지도 않기 때문에 부르트 포스로 도전해 볼 만하다. 예를들어 단어에 나열된 알파벳이 

A B C D E F G H I J 이라면

0 1 2 3 4 5 6 7 8 9 로 각각의 알파벳과 매핑할 수 있고 가능한 조합의 개수는 0 ~9 숫자 들로 구성되는 10개 짜리 수열의 개수 이므로 10! ( 3,628,800 ) 에 불과하기 때문이다.

 

문제를 풀기위한 세부 단계는 아래와 같다.

1. 나열된 알파벳들을 읽어 서로다른 알파벳 배열을 만든다.

2. 알파벳들과 매칭할 숫자 집합을 구성한다. 가장 큰 숫자이기때문에 만약 알파벳들의 개수가 10개 미만일 경우 큰수 부터 매핑하면 된다. 예를들면 A B C D 일 경우 9 8 7 6 으로 매핑하면 된다.

3. 매핑된 숫자들의 가능한 모든 조합을 순회하면서 가장 큰값을 업데이트한다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;


int calc(string &s, map<char, int> &wm, vector<int> &numList)
{
	int result = 0;
	for (auto &c : s)
	{
		result *= 10;
		result += numList[wm[c]];
	}
	return result;
}


int main()
{
	int w;
	cin >> w;
	string s[10];
	map<char, int> wm;
	int order = 9;

	vector<int> numList;
	for (int i = 0; i < w; i++)
	{
		cin >> s[i];
		for (auto &c : s[i])
		{
			if (wm.find(c) == wm.end())
			{
				wm[c] = 9 - order;
				numList.push_back(order--);
			}
		}
	}
	int result = 0;
	do
	{
		int sum = 0;
		for (int i = 0; i < w; i++)
		{
			sum += calc(s[i], wm, numList);
		}
		result = max(result, sum);
	} while (prev_permutation(numList.begin(), numList.end()));
	cout << result << endl;
	return 0;
}