[백준] 1132 - 합

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

1132번: 합

 

예제 입력 1을 함께 보자.

2
ABC
BCA

이 문제의 모든 예제는 하나의 수식으로 표현할 수 있는데, 위의 예제를 수식으로 표현하면 다음과 같다.

100 * A + 10 * B + 1 * C + 100 * B + 10 * C + 1 * A

= 101 * A + 110 * B + 11 * C

이렇게 수식을 만들면 당연히 B - A - C 순으로 큰 수가 배정되어야 한다고 볼 수 있다.

 

하지만 문제에서 0으로 시작하는 수는 없다라고 하고, 친절하게 예제 입력 3에서 그 예시를 보여준다.

2
ABCDEFGHIJ
J

= 1000000000 * A

+ 100000000 * B

+ 1000000 * C

+ 1000000 * D

+ 100000 * E

+ 10000 * F

+ 1000 * G

+ 100 * H

+ 10 * I

+ 2 * J

인데, J가 숫자의 처음에 오는 경우가 생겨서 0을 배정할 수 없다.

입력으로 적어도 한 알파벳은 수의 가장 처음에 주어지지 않는다고 했으므로, 입력에 오류가 나는 경우는 없고, 따라서 이런 경우에 어떠한 알파벳은 가중치가 최소가 아니더라도 0을 배정받아야 한다.

 

여기서 중요한 점은 어떠한 알파벳을 찾는 것인데, 잘 생각해 보면 숫자의 처음에 오는 경우가 없으면서 가중치가 가장 적은 것을 택하고 0을 배정하고, 그 아래의 알파벳들에게 배정할 숫자를 1씩 증가시키면 된다.

pair<long long, bool> a라는 변수를 선언하고, 가중치가 first 이면서, second = true일 때 숫자의 처음에 오는 경우가 있는 알파벳이라고 했을 때, 예제 입력 4를 표현하면 다음과 같다.

여기서 (111111111, false)에 0을 배정하고(맨 밑으로 보내고) 그 아래에 숫자를 1씩 더 배정하면 다음과 같이 될 것이다.

이후 9부터 순서대로 숫자를 배정하면 된다.

 

#include <algorithm>
#include <iostream>
using namespace std;

string s[50];
int n;
pair<long long, bool> a[10];

int main() {
    cin >> n;
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        cin >> s[i];

        long long p = 1;
        for (int j = s[i].length() - 1; j >= 0; j--) {
            if (j == 0) {
                a[s[i][j] - 'A'].second = true;
            }
            if (!a[s[i][j] - 'A'].first) {
                cnt++;
            }
            a[s[i][j] - 'A'].first += p;
            p *= 10;
        }
    }

    sort(a, a + 10, [](auto &a, auto &b) { return a.first > b.first; });

    long long t = 9;
    long long ans = 0;

    if (cnt == 10 && a[9].second == true) {
        for (int i = 8; i >= 0; i--) {
            if (a[i].second == false) {
                pair<long long, bool> temp = a[i];
                for (int j = i; j < 9; j++) {
                    a[j] = a[j + 1];
                }
                a[9] = temp;
                break;
            }
        }
    }
    for (int i = 0; i < 10; i++) {
        ans += (t--) * a[i].first;
    }
    cout << ans;
}