백준 1339번 : 단어 수학 (C++)

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

1339번: 단어 수학

 

가능한 모든 경우의 수 할당으로 합을 계산해서 최대의 합을 구하는 방법,

GCF+ACDEB를 100G+10C+1F+10000A+1000C+100D+10E+1B로 생각해서 구하는 방법

두 가지를 정리해보겠습니다.

 

코드1

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
bool alpha[26];
int alphanum[26];
int num[10]={9,8,7,6,5,4,3,2,1,0};
string arr[10];
int res,n;
 
void check(string str)
{
    for(int i=0;i<str.size();i++)
    {
        alphanum[str[i]-65]=num[i];
    }
    int sum=0;
    for(int i=0;i<n;i++)
    {
        int now=0;
        for(int j=0;j<arr[i].size();j++)
        {
            now*=10;
            now+=alphanum[arr[i][j]-65];
        }
        sum+=now;
    }
    if(res<sum)res=sum;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    string list;
    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;
        arr[i]=str;
        for(int j=0;j<str.size();j++)
        {
            if(alpha[str[j]-65]==false)
            {
                alpha[str[j]-65]=true;
                list+=str[j];
            }
        }
    }
    sort(list.begin(),list.end());
    do
    {
        check(list);
    }while(next_permutation(list.begin(),list.end()));
    cout<<res;
    return 0;
}

 

풀이1

 arr 배열에 입력받은 단어들을 저장하고 list 변수에는 입력받은 단어 중에서 중복되는 알파벳을 제외하고 저장한다. list 변수가 알파벳순으로 되도록 sort 함수로 정렬해준다. 그 뒤에 do-while 문과 next_permutation 함수를 이용하여 모든 순열의 합을 계산하여 최대의 합을 구한다. 각 숫자 할당의 합을 구하는 check 함수는 각 알파벳의 할당 수를 alphanum 배열에 지정해주고(앞의 수부터 9, 8, 7,,,,,0을 단어의 길이만큼 지정) 각 단어의 한 글자의 수마다 10을 곱하여 더해주면서 합을 구하고 최대의 합을 전역변수로 선언된 res 변수에 저장되게 한다.

 

코드2

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int alpha[26];
int main() {
    int n;
    string str;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>str;
        int x=1;
        for(int j=str.size()-1;j>=0;j--)
        {
            alpha[str[j]-65]+=x;
            x*=10;
        }
    }
    sort(alpha,alpha+26);
    int num=9;
    int sum=0;
    for(int j=25;j>=0;j--)
    {
        if(alpha[j]==0)break;
        sum+=alpha[j]*num;
        num--;
    }
    cout<<sum;
    return 0;
}

 

풀이2

  각 단어를 입력받을 때마다 단어가 ABCD라면 alpha 배열의 A 알파벳에 해당하는 인덱스인 0에는 1000,B인덱스에는 100, C인덱스에는 10, D인덱스에는 1을 넣어준다. 모든 단어를 입력받고 해당 값들을 alpha 배열에 저장한 후에 alpha 배열을 정렬하고 alpha 배열의 값이 큰 순서대로 9, 8, 7, 6,,,, 0의 값을 할당해서 합을 구해준다.