1339 단어 수학
알고리즘(브루트포스, 그리디)
1
2
3
4
5
6
7
8
9
10
- 브루트포스
1. 어떤 알파벳이 나왔는지 기록하고, 거기에 맞춰 알파벳의 종류의 개수만큼 모든 가능한 수를 뽑아 검사한다.
- 그리디
1. 들어오는 단어를 알파벳 단위로 분류하고 다음처럼 자릿수를 곱해준다.
ABC -> 100A + 10B + C
BCA -> 100B + 10C + A
2. 그리고 모든 단어를 더해준다.
101A + 110B + 11C
3. 이를 앞에 자릿수대로 내림차순 정렬하면, 가장 커야할 수가 나오고, 그에따라 수를 부여하고 계산하면 된다.
110B + 101A + 11C
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N, acheck[26], index, result;
string word;
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> word;
int digit = 1;
for (int j = word.size() - 1; j >= 0; j--) {
if (acheck[word[j] - 'A'] == 0)
index++;
acheck[word[j] - 'A'] += digit;
digit *= 10;
}
}
sort(acheck, acheck + 26);
int cur = 9 - index + 1;
for (int i = 26 - index; i < 26; i++) {
result += acheck[i] * cur;
cur++;
}
cout << result;
}