[ 백준 1339 ] 단어수학 (C++)

백준의 단어수학(1339) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 사실 이 문제는 백트래킹 문제인제, 본인은 수학으로 이 문제를 해결하였다.

   문제 풀이 방법은 이렇다. 주어진 식을 10의 거듭제곱을 붙여서 모두 더해주는 것이다.

   예를 들어서 설명해보겠다.

   ABC

   DEFG 가 있다고 생각해보자.

   위의 식을 10의 거듭제곱을 붙여서 표현해보면

   "100A + 10B + C" + "1000D + 100E + 10F + G"로 나타낼 수 있고, 계산을 해보면 "1000D + 100A + 100E + 10B + 10F + C+ G"

   로 표현할 수 있다.

   이 상태에서, 가장 큰자리 숫자들 부터 9, 8, 7을 순서대로 넣어주면 자연스레 최댓값이 나오게 된다.

   하나의 예만 더 알아보자.

   ABC

   ADFG 라는 식이 있다고 생각해보자. 이 식을 10의 거듭제곱을 붙여서 표현해보면

   "100A + 10B + C" + "1000A + 100D + 10F + G"가 되고, 이를 계산해보면 "1100A + 100D + 10B + 10F + C + G"가 된다.

  

2) 이를 어떻게 표현할지 알아보자. 본인은 Alphabet[] 이라는 1차원 배열을 하나 만들어 두었다.

   이 후에, A부터 J 까지의 계수를 저장해 주었다.

   위에서 말한 ABC , ADFG 를 더하는 예제로 설명을 하자면

   ABC에서 A = 100 , B = 10, C = 1이라는 값을 가지게 된다.

   그럼 Alphabet[A] = 100, Alphabet[B] = 10, Alphabet[C] = 1로 저장해 주었다.

   물론, Alphabet[A]는 설명을 돕고자 한 말이고, A를 숫자로 바꾼 Alphabet[0] 에 저장해 주었다.

   ADFG 에서는 A = 1000, D = 100 , F = 10, G = 1의 값을 가지게 되고, 기존의 배열에다가 더해주었다.

   즉, Alphabet[A] = 100 + 1000 = 1100 이 되고, Alhabet[D] = 100, Alhabet[F] = 10, Alphabet[G] = 1 로 설정이 되있을것이다.

  

   이후, 이 알파벳 배열을 내림차순을 정렬을 시키는 것이다.

   내림차순 정렬을 시키게 되면, 1100 100 100 100 ... 1 이런식으로 정렬이 될 것이다.

   이후, 순서대로 9 , 8, 7을 곱하면서 더해주면 그 값이 최대값이 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
 
#define endl "\n"
using namespace std;
 
int N;
int Alphabet[26];
vector<string> V;
 
bool Cmp(int A, int B)
{
    if (A > B) return true;
    return false;
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string Inp; cin >> Inp;
        V.push_back(Inp);
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        string S = V[i];
        int Len = S.length();
        int Pow = 1;
 
        for (int j = Len - 1; j >= 0; j--)
        {
            int Tmp = S[j] - 'A';
            Alphabet[Tmp] = Alphabet[Tmp] + Pow;
            Pow = Pow * 10;
        }
    }
    sort(Alphabet, Alphabet + 26, Cmp);
    
    int Answer = 0;
    int Num = 9;
    for (int i = 0; i < 26; i++)
    {
        if (Alphabet[i] == 0) break;
        Answer = Answer + (Alphabet[i] * Num);
        Num--;
    }
 
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}