1. 문제 분석하기

1.1. 문제 의도

• 모든 경우의 수를 구한 뒤 최적해를 구하는 bruteforce 문제입니다.

2. 문제 해결하기

• 이 문제는 두 가지 방법으로 해결할 수 있습니다.
  1. Bruteforce 방법: 알파벳은 최대 10개이므로 $10! = 1,034,768$
  2. Greedy 방법: 높은 자릿수에 있는 알파벳 순으로 큰 숫자를 할당해줍니다.

1. Bruteforce 방법

• 단어 N개를 읽고, 등장하는 모든 알파벳을 구합니다.
  • 이때 알파벳이 꼭 A부터 순서대로 등장한다는 법은 없습니다!! Q나 Z같은 알파벳도 나올 수 있습니다! 주의!
• 등장하는 알파벳에 대해 0~9까지 숫자를 부여합니다.
• next_permutation()함수를 이용해 모든 조합에 대해 합을 계산합니다.
• 계산한 합들 중 최대값을 구합니다.

2. Greedy 방법

• 단어 N개를 읽고, 등장하는 알파벳에 대해 자릿수를 더해줍니다.
  • GAFA = alpha[‘G’ - ‘A’] = 1000, alpha[‘A’ - ‘A’] = 100, alpha[‘A’ - ‘F’] = 10 , alpha[‘A’ - ‘A’] = 101
• alpha 배열을 오름차순으로 정렬합니다.
• alpha배열을 끝에서부터 9, 8, 7 씩 곱합니다.
  • GCF + ACDEB
    • A(alpha[0]) = 10,000
      B(alpha[1]) = 1
      C(alpha[2]) = 1,010
      D(alpha[3]) = 100
      E(alpha[4]) = 10
      F(alpha[5]) = 1
      G(alpha[6]) = 100
    • 정렬
      0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 10 100 100 1010 10000
    • 끝에서부터 9, 8, 7 … 대입
    • 90000 + 8080 + 700 + 600 + 50 + 4 + 3 = 99437

3. 코드

1. Bruteforce 방법

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

int N, alpha[26], mappingTable[10], answer;
char words[10][9];

int cvt2Num(char str[9]) {
	int ret = 0, idx = 0;
	while (str[idx] != '\0') ret = ret * 10 + mappingTable[alpha[str[idx++] - 'A']];
	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
    	// alpha와 mappingTable 배열 초기화
	for (int i = 0; i < 26; ++i) alpha[i] = -1;
    	for (int i = 0; i < 10; ++i) mappingTable[i] = i;
    	// 단어 입력받기.
	for (int i = 0, k = 0; i < N; ++i) {
		int j = 0;
		cin >> words[i];
        	// words[i] 속 알파벳이 mappingTable의 k번째 인덱스에 매핑.
		while(words[i][j] != '\0') {
			if (alpha[words[i][j] - 'A'] == -1) alpha[words[i][j] - 'A'] = k++;
			j++;
		}
    	}	
	do {
		int sum = 0;
		for (int i = 0; i < N; ++i) sum += cvt2Num(words[i]);
		answer = max(answer, sum);
	} while(next_permutation(mappingTable, mappingTable + 10));
	cout << answer;
}

2. Greedy 방법

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N, len, ans, alphabet[26];
int main() {
	char str[9];
	scanf("%d", &N);
	while (N--) {
		scanf("%s", str);
		len = strlen(str);
          	// 모든 단어 속에서 특정 알파벳이 위치했던 자릿수를 더한다.
		for (int i = len - 1, j = 1; i >= 0; --i, j *= 10)
			alphabet[str[i] - 'A'] += j;
	}
	sort(alphabet, alphabet + 26);
	for (int i = 0; i < 10; ++i) ans += alphabet[25 - i] * (9 - i);
	printf("%d", ans);
}

4. 결과

1. Bruteforce 방법

2. Greedy 방법