[백준 알고리즘/C++/그리디] 1339 단어 수학

 

 

단어 수학 문제는 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다

같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 문제

 

 

너무 오랜만에 하려니까 살짝 당황스러웠던 문제

침착하게 키보드 줘패면서 풀어보니 생각보다 어렵지 않다

 

풀이

1. 단어가 입력됐을 때 각 알파벳의 비중(?)이 얼마나 큰지 구한다

2. 정렬한다

3. 차례대로 9~1까지 곱해서 더한다

 

예를 들어 GCF, ACDEB가 입력됐다면 아래와 같이 풀 수 있다

 

1, 2번 과정

A = 10000

C = 1000 + 10

D = 100

G = 100

E = 10

B = 1

F = 1

 

3번 과정

A = 10000 * 9

C = 1000 + 10 * 8

D = 100 * 7

G = 100 * 6

E = 10 * 5

B = 1 * 4

F = 1 * 3

A+C+D+G+E+B+F = 99437

 

정답 99437을 확인할 수 있음

코드로 표현하는건 어렵지 않다 (사실 좀 멈칫거림)

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int res = 0;
vector<string> v;
int alpha[26];
 
void func() {
    for (int i = 0; i < v.size(); i++) {
        int temp = 1;
        for (int j = v[i].size() - 1; j >= 0; j--) {
            int val = v[i][j] - 'A';
            alpha[val] += temp;
            temp *= 10;
        }
    }
 
    sort(alpha, alpha + 26);
    int num = 9;
    for (int i = 25; i >= 0; i--) {
        if (alpha[i] == 0) break;
        res += alpha[i] * num--;
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    string str;
 
    cin >> n;
    while (n--) {
        cin >> str;
        v.push_back(str);
    }
 
    func();
    cout << res;
}