https://www.acmicpc.net/problem/1132
boj 1339 단어 수학
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있
whyeskang.com
이 문제와 접근 방식이 같습니다.
다만 다른점은 위 문제와 다르게 첫 글자에 0이 올 수 없다는 것을 추가로 고려해야 합니다.
알파벳의 각 자릿수의 합은 문자열을 뒤에서부터 1, 10, 100, 1000 ... 이렇게 10씩 곱한 값을 더해주시면 됩니다.
그 후에 첫번째에 오는 알파벳을 체크했다가 0을 부여 받을 알파벳을 선정하도록 합니다.
선정 로직은 zeroChk가 false인 알파벳들 중 가장 작은 자릿수를 가진 알파벳에 0을 넣으면 됩니다.
나머지는 각 자릿수의 합 배열 (num)을 내림차순으로 정렬하여 큰 수부터 값을 더해주시면 되겠습니다.
알파벳이 10개 미만으로 사용되었더라도 나머지 알파벳은 zeroChk가 false이고, 자릿수가 0이므로 다른 예외처리 없이 구할 수 있습니다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <iostream>
#include <string>
#include <algorithm>
#define MAX_N 51
#define MAX_M 10
using namespace std;
typedef long long ll;
string list[MAX_N];
ll num[MAX_M];
bool zeroChk[MAX_M];
int N;
void init() {
int zIdx = -1;
for (int i = 0; i < N; i++) {
int len = list[i].size();
ll d = 1LL;
for (int j = len - 1; j >= 0; j--) {
num[list[i][j] - 'A'] += d;
d *= 10LL;
}
zeroChk[list[i][0] - 'A'] = true;
}
for (int i = 0; i < MAX_M; i++) {
if (zeroChk[i]) continue;
if (zIdx == -1 || num[zIdx] > num[i]) zIdx = i;
}
num[zIdx] = 0;
}
void func() {
init();
sort(num, num + MAX_M, [](ll a, ll b) {
return a > b;
});
ll ret = 0;
ll n = 9;
for (int i = 0; i < MAX_M; i++) {
ret += (n * num[i]);
n--;
}
cout << ret << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 23559 밥 (0) | 2024.07.11 |
|---|---|
| boj 2140 지뢰찾기 (0) | 2024.07.10 |
| boj 25381 ABBC (0) | 2024.07.07 |
| boj 28325 호숫가의 개미굴 (0) | 2024.07.06 |
| boj 14464 소가 길을 건너간 이유 4 (0) | 2024.07.05 |