문제 요약

본문 요약
단어 수학 문제는 N개의 단어로 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10), 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

---

풀이

이 문제는 아래의 아이디어로 요약된다.

1. 어차피 수들의 합만 최대로 만들면 된다.
2. ABCD란 수는 1000 A + 100 B + 10 * C + D로 표현 가능하다.
3. 수들의 합이 최대가 되는 경우는 위처럼 분리했을 때 자리수 정보가 높은 문자부터 높은 수를 순차적으로 부여하는 경우이다.

예시를 보며 설명하겠다. AABB + CABC라는 식은 아래처럼 표현이 가능하다.

AABB + CABC = (1200 * A) + (21 * B) + (1000 * C)

자리수 정보라는 단어를 문자 앞에 곱해진 수라고 정의하겠다.
그러면 자리수 정보를 높은 순으로 나열하면 A B C가 될 것이다.
그러므로 A에는 9, C에는 8, B에는 7을 부여했을 때가 만들 수 있는 가장 큰 수이다.

AABB + CABC = (1200 * A) + (21 * B) + (1000 * C)
= (1200 * 9) + (21 * 7) + (1000 * 8) = 17947

나는 자리수 정보를 표현하기 위해, ascii라는 127크기의 배열을 만들었다.
A부터 Z까지의 문자는 1부터 127안의 아스키코드 값을 가진다는 것을 이용하여 해당 문자를 표현하였다.
가령 ascii['A']는 ascii[65]와 동치이다.
일종의 해싱 혹은 딕셔너리라고 생각하면 되겠다.

다시 위의 AABB + CABC의 예시에서, 해당 값이 들어왔을 때, ascii배열에서 A의 위치(ascii[65])에는 1200이 저장된다.

이렇게 자리수 정보를 구해줬으면 큰 순으로 9부터 곱해준 후 더하면 끝이다.

---

코드:

#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
using namespace std;

int main()
{
	int n, max, alpha, ans, ascii[128] = {0};
	string arr[10];

	ans = 0;
	cin >> n;
	// 입력 및 ascii 배열에 자리수 정보를 입력(n 번째 자리에 몇 번 들어왔는지의 정보가 들어감)
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		for (int j = 0; j < arr[i].length(); j++)
			ascii[(int)arr[i][j]] += pow(10, arr[i].length() - j - 1);
	}
	// 가장 큰 ascii 배열의 원소에 저장된 자리수 정보에 9부터 1까지 순서대로 곱해준 후 덧셈
	for (int k = 9; k >= 0; k--)
	{
		max = 0;
		alpha = 0;
		for (int i = 'A'; i <= 'Z'; i++)
		{
			if (max < ascii[i])
			{
				max = ascii[i];
				alpha = i;
			}
		}
		ans += k * ascii[alpha];
		ascii[alpha] = 0;
	}
	cout << ans;
}