백준 1339번 단어 수학[C++]

1. 개요

 안녕하세요. 오늘 풀어본 문제의 유형은 그리디입니다. 하지만 저는 브루트포스로 풀었습니다. 정확한 분석을 한 것은 아니었지만 단어의 개수와 길이, 알파벳의 수가 크지 않아 가능하다고 판단했습니다. 그런데 어째서 가능한지 분석할 필요가 있어 작성해 보겠습니다.

 

 주어진 조건에서 최악의 경우를 상정해 보면 단어의 개수가 10개이고 길이는 모두 8, 서로 다른 알파벳은 10개라고 해봅시다. 알파벳에 0부터 9까지 숫자를 부여하는 것은 순열 계산으로 10!입니다. 그리고 단어를 수로 변환하는 과정은 10 * 8개의 연산을 통해 계산할 수 있으므로 시간복잡도는 O(10! * 10 * 8)입니다. 10! * 10 * 8은 약 2억 9천입니다. 시간제한이 넉넉하게 2초이므로 브루트포스로도 풀이할 수 있습니다.

 

 저는 당연히 이 문제가 브루트포스 유형의 문제라고 판단해 풀었습니다. AC를 받은 후 유형이 그리디인 것을 확인했고 시간이 넉넉할 때 그리디로도 풀어보려고 합니다.

 

2. 문제 풀이

  알파벳에 숫자를 할당할 배열 a를 선언합니다. 초기값은 -1이고 단어를 입력받습니다. 이때 26개의 알파벳 중 단어에 포함된 알파벳이면 0을 할당해 사용하는 단어임을 표시하면서 알파벳을 문자열에 삽입하여 관리합니다.

 

 숫자를 할당하는 작업은 next_permutation()이라는 순열을 계산해 주는 STL 함수를 사용할 겁니다. 이를 위해서 mask 배열에 할당할 숫자 정보를 미리 준비해야 합니다. 단어에 포함된 알파벳이 10개라면 0부터 9까지 값을 삽입하여 주시고 5개라면 5부터 9까지 값을 삽입해 주시면 됩니다.

 

 이후 next_permutaion으로 순열을 계산하고 그 순열에 할당된 숫자를 사용하여 단어를 수로 변환하여 더해주시고 그중 최댓값을 찾아 출력하시면 풀이하실 수 있습니다.

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
vs words;

string k;

vi a;

int main() {
    fastio(nullptr, false);

    cin >> n;

    vs (n).swap(words);
    vi ('Z' - 'A' + 1, -1).swap(a);

    for(auto &str : words) {
        cin >> str;

        for(auto &x : str) {
            if(a[x - 'A'] == -1) {
                a[x - 'A'] = 0;
                k.pb(x);
            }
        }
    }

    ll ans{};
    vi mask(sz(k));
    iota(all(mask), 10 - sz(k));
    do {
        for(int i = 0; i < sz(k); i++) {
            a[k[i] - 'A'] = mask[i];
        }

        ll tot{};
        for(auto &str : words) {
            ll cur{};
            for(auto &x : str) {
                cur *= 10;
                cur += a[x - 'A'];
            }
            tot += cur;
        }

        ans = max(ans, tot);
    } while (next_permutation(all(mask)));

    cout << ans;
}

 

4. 제출 결과