[BOJ/백준][Gold4] 1339 : 단어 수학 (C++)

www.acmicpc.net/problem/1339

 

 

[난이도] Gold4

[유형] Greedy / 완전탐색

 

[풀이]

1. Greedy

모든 문자가 1이라고 가정하고 각 문자의 자리수를 고려한 총합이 최대가 되는 문자에 9부터 차례로 할당했을 때의 합을 출력한다.

 

2. 완전탐색

k가 총 문자 종류의 수일 때 9-k+1 ~ 9 의 문자를 각 문자에 할당할 수 있는 모든 경우의 수를 고려하면 된다. 10!이므로 시간초과나지 않는다. (stoi를 사용했을 경우에 시간초과가 났음)

 

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int N,a[27],ans,cnt;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int j=0;j<s.size();j++){
            int sz = s.size()-j-1;
            int k = 1;
            while(sz--) k*=10;
            a[s[j]-'A'] += k;
        }
    }
    vector<int> v;
    for(int i=0;i<26;i++) if(a[i]) v.push_back(a[i]);
    sort(v.begin(),v.end());
    int j=0;
    for(int i=9-v.size()+1;i<=9;i++) ans += i*v[j++];
    cout << ans;
}


// #include <algorithm>
// #include <vector>
// #include <string>
// #include <iostream>
// #include <set>
// using namespace std;
// int N,cvt[27],ans;
// vector<string> a;
// int main(){
//     set<char> s;
//     scanf("%d",&N);
//     a.resize(N);
//     for(int i=0;i<N;i++){
//         cin >> a[i];
//         for(auto c : a[i]) s.insert(c);
//     }
//     vector<int> v;
//     for(int i=0;i<s.size();i++) v.push_back(9-i);
//     reverse(v.begin(),v.end());
//     do{ 
//         int i=0;
//         for(auto c : s) {
//             cvt[c-'A']=v[i++];
//         }
//         int sum = 0;
//         for(auto str : a){
//             int k=1;
//             for(int j=str.size()-1;j>=0;j--) {
//                 sum+=cvt[str[j]-'A']*k;
//                 k*=10;
//             }
//         }
//         ans = max(ans,sum);
//     }while(next_permutation(v.begin(),v.end()));
//     cout << ans;
// }

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1339.cpp