백준 1339번 C++ 풀이

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

시간 제한	메모리 제한	solved.ac 티어
2초	256MB	골드 4

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

---

처음에는 길이가 긴 숫자의 왼쪽부터 9, 8, 7...씩 줄여가며 번호를 부여하려고 했다. 하지만 생각해보니 예외상황이 너무 많을 것 같았고, 다른 풀이를 생각하기 생각했다. 그래서 생각을 다르게 하여 이 수를 쪼개보기로 했다.

AAA라는 숫자는 사실 100A + 10A + A로 나타낼 수 있다. 입력받은 단어를 위와같이 바꾸고, 각 알파벳에 대해 이렇게정리한다. 이후에는 정말 우리가 하던 것처럼 산술 연산을 한다.

 

예를 들어, ABC + BCA라고 하면 (100A + 10B + C) + (100B + 10C + A)로 나타낼 수 있고, 각 알파벳에 대해 묶으면

101A + 110B + 11C이다. 계수가 높은 순서대로 9, 8, 7....의 숫자를 부여하면 가장 큰 합이 될 것이다.

 

#include <bits/stdc++.h>
using namespace std;

int n;
vector<string> words;

void input() {
    cin >> n;
    words.resize(n);
    for(auto& x : words) cin >> x;
}

void sol() {
    int use_alpha[26] = {0, };
    int result = 0;
    int pow;

    for(auto word : words) {
        pow = 1;
        reverse(word.begin(), word.end());
        for(auto ch : word) {
            use_alpha[ch - 'A'] += pow;
            pow *= 10;
        }
    }

    sort(use_alpha, use_alpha + 26, greater<>());
    for(int i = 0; i < 10; i++) {
        result += use_alpha[i] * (9 - i);
    }
    cout << result;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}