1. 문제 분석하기
1.1. 문제 의도
- 모든 경우의 수를 구한 뒤 최적해를 구하는 bruteforce 문제입니다.
2. 문제 해결하기
- 이 문제는 두 가지 방법으로 해결할 수 있습니다.
- Bruteforce 방법: 알파벳은 최대 10개이므로 10!=1,034,768을 모두 구한 뒤 최적해를 찾습니다.
- 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;
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];
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 방법