백준 1339 - 단어 수학(그리디 알고리즘)

문제

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

단어 수학 문제는 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

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

 

 

 

---

1. 문제 해석

알파벳을 숫자로 치환할 때, 그 알파벳들의 덧셈 연산의 합이 최대가 되도록 만드는 문제이다. 

 

그리디 알고리즘일 거라고 생각해서, 증명하기 위한 논리를 세워보았다. 

 

* 그리디 알고리즘 증명하기 >> [링크]

 

첫 시도는 실패했는데, 그 논리 흐름은 다음과 같다. 

1. 자릿수가 큰 알파벳부터 큰 숫자를 지정하면 내가 원하는 최적해에 도달할 수 있을 것이다!

이러한 조건의 경우, 그리디 알고리즘이 성립하는 지 생각해보자 .

처음엔  자릿수가 있을 때 _ _ _ _  + _ _ _ _ 

T _ _ _  + _ _ _ _  ...   < T-1 _ _ _   + _ _ _ _  .. 가 되는 경우가 없다는 것을 증명하려고 했다. 

 

-> T는 양수이고, 문제 조건에 따라 각 자릿수는 8자리 이하이며 주어지는 숫자는 10개이하이고 모든 알파벳의 종류도 10개 이하이다. 

-> 아무리 숫자가 많아도 10개가 최대이니, T _ _ _. +. _ _ _ _ ...   보다 T-1 _ _ _ + ... 가 더 크려면

T-1 로 첫자릿수는 하나가 적어도, 그 다음에 오는 숫자가 T로 더 크고, 그 개수 최대한 많아져서 10개에 도달하면

T T-1 ... 인 숫자는 (T * 1000 + (T-1) * 100  + _ * 10 +  _* 1) + T-1 * 100 *9인 반면

T-1 T ... 인 숫자는 ((T-1) * 1000 + T  * 100 + _ * 10 +  _ * 1) + T * 100 * 9로,  초기 자릿수가 같아진다. 

 

무슨 말인가 하면, 

 

 

그나마 같아지는 경우가 최대 10개이니, 위  조건문이 참이라는 결론에 도달했다. 

 

하지만 이건 결론적으로 틀린 증명이다. 

애초에 문제는 문제 조건에 일반화 된 경우가 아니었기 때문에 애초에 참이라고 해봤자 특수한 경우에 해당했던 것이다. 

이게 틀렸다는 건 다음과 같은 반례를 통해 알게 되었다. 

AB
BB
BB

98 + 88 * 2 = 284 (A = 9, B = 8)

89 + 99* 2 = 287 (A = 8, B = 9)

문제는 자릿수의 문제가 아니라, 얼마나 더해졌느냐가 더 중요하다는 것이다. 

 

 

다시 제대로 증명해보자.

그리디 알고리즘은 해당 조건에 대해 그 조건을 포함하는 최적해가 반드시 존재함을 보이는 "그리디 속성 증명"과

부분의 문제 해결을 통해 전체 문제를 해결할 수 있음을 보이는 "부분 구조 문제"를 증명하면 된다. 

 

각 알파벳들의 합을 숫자로 표현해보면 다음과 같다.

2
GCF
ACDEB

입력이 있다면, 

 

총합은 A * 10000  + C * 1000 + 100*G + 100 * D. + 10*C + 10* E + F + B 이다.

이에 대해 임의의 A,B,C,D,E,F 에 대해

A * a1 + B * b1 + C * c1 + D * d1 + E* e1 + F * f1의 총합이 있다고 하자 .

이때 x1의 큰 순 서대로 9 ,8 ,7 ,. .을 배정한다는 것이 내가 이번에 규정하는 그리디의 원칙이다. 

 

이때 a1 >= b1 >= c1 >= d1 >= e1 >= f1 일때, 

x1의 값이 큰 알파벳부터 X에 큰 숫자를 넣었을 때 이런 조건을 포함하는 최적해가 존재한다고 증명해보자. 

 

이를 증명하는 쉬운 방법 중 하나는, 그 조건에 해당하지 않는 최적해가 존재한다고 가정할 때, 
그 최적해로부터 다시 그리디의 조건을 만족하는 최적해를 도출해내거나, 
그 최적해가 존재할 수 없는 모순임을 밝히는 방법이 있다.

 

 

위의 조건을 해당하지 않는 최적해가 존재한다고 할 때, 

a1 >= b1 임에도 불구하고 A에 더 작은 숫자가 들어가는 경우가 그 예시일 것이다. 

이때, A < B 일 것이고

합은 여전히 A * a1 + B * b1 + C * c1 + D * d1 + E* e1 + F * f1 일 것이므로, 

A  = t, B = t+1이라고 하면

 t * a1 + (t+1) * b1 + C * c1 + D * d1 + E* e1 + F * f1   <=  (t+1)* a1 + (t) * b1 + C * c1 + D * d1 + E* e1 + F * f1  이 된다.

왜냐하면 a1 >= b1이기 때문에 더 큰 수가 곱해지면 값이 더 커질 수 밖에 없기 때문이다. 

 

따라서, a1 >= b1 >= c1 >= d1 >= e1 >= f1 (x1은 X의 계수) 의 조건에서 A < B 인 최적해가 존재한다는 가정은 답에 모순이 되고, 

이는 A > B 가 조건인 최적해가 반드시 존재한다는 결론에 도달한다. 

또한, 부분구조의 증명도 쉽게 된다. 

A에 가장 큰 수를 대입했다면, 그 다음으로 큰 계수를 갖는 B는 그 다음 작은 수를 대입하고, 이를 반복하면 전체 최적 해에 도달할 수 있다는 것이 자명하다.

 

2.구현 

 그리디를 증명했고, 이 그리디 조건에 의해 짠 코드는 다음과 같다. 

 

#include <unistd.h>
#include <stdlib.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>

int N;
using namespace std;
//vector <pair< pair<string, int>, int> >  num;
vector <string> num;
long long selected[27][2]; //각 알파벳의 자릿수합 과 값을 저장할 것임.

long long square(int n, int r)
{
    if(r == 0)
        return 1;
    return square(n , r-1)*n;
}

void input()
{
    string str;
    for(int i=0;i<N;i++)
    {
        cin >> str;
        num.push_back(str);
        for(int j=0;j<str.length();j++)
        {
            selected[str[j] - 'A'][0] += square(10, str.length()-j-1);
        }
    }

    for(int i=0;i<27;i++)
        selected[i][1] = -1;
}

int findmax() //최대 합을 가진 알파벳을 아직 값을 안 정한 알파벳중에서 골라서 반환
{
    long long max = -1;
    int idx = 0;
    for(int i=0;i<27;i++)

        if(selected[i][1] == -1 && selected[i][0] > 0)//값이 안정해지고 input에는 존재하는 알파벳일 경우 후보. (다 채우고 없으면 max == -1)
        {
            if(selected[i][0] > max)//매번 갱신: 0이상의 값이기때문에 놓치지는 않음
            {
                max = selected[i][0];
                idx = i;
            }
        }

    if(max == -1)
        return -1;
    return idx;
}

void solve()
{
    int n = 9;
    int cnt=  0;
    while(1)
    {
        int alpha = findmax();
//        cout << alpha <<"\n";
        if(alpha != -1) {
            selected[alpha][1] = n;
//            cout << (char)(alpha + 'A') << " : " << selected[alpha][0]  << " "<<n<< "\n";
            n--;

        }
        else
            break;
    }

    unsigned long long sum = 0;
    for(int i=0;i<N;i++)
    {
        string str = num[i];
        long long tmp = 0;
        for(int j=0;j<str.length();j++)
        {
            tmp = tmp * 10 +  selected[str[j]- 'A'][1];
//            cout << tmp <<"\n";
        }
        sum += tmp;
    }
    cout << sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    input();
    solve();//각 알파벳이 의미하는 값 찾기.
}