백준 1339 / 단어 수학

순열, 백트래킹을 이용한 문제.

처음에 풀땐 굉장히 헤맸다. 

들어간 알파벳의 우선순위를 정하고 우선순위에 맞게 숫자를 부여하는 방식을 사용했었는데, 계속 반례에 걸리는 듯하여

순열을 사용해서 풀어보았다.

여기서 처음 알게된 유용한 함수가 있다.

바로 vector안의 중복된 것들을 모두 지워주는 함수.

v.erase(unique(v.begin(), v.end()), v.end());

unique 함수는 vector 내부의 중복된 값들을 맨 뒤로 정렬하고, 자신이 바꾼 vector의 end() 부분을 반환한다.

그 부분만 erase해주면 중복제거가 된다.

또 string s 에 대해

for(char x : s)를 사용하면 x가 s의 한 글자씩 입력받는다는 사실도 처음 알았다.

두 개다 유용한 함수니 기억해두어야겠다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
 
using namespace std;
char alpha[256];
 
int calc(vector<string> &word, vector<char> &letter, vector<int> &d) {
    int m = letter.size();
    int sum = 0;
 
    for (int i = 0; i < m; i++) {
        alpha[letter[i]] = d[i];
    }
 
    for (string s : word) {
        int now = 0;
        for (char x : s) {
            now = now * 10 + alpha[x];
        }
        sum += now;
    }
 
    return sum;
}
 
int main() {
    
    int n;
    
    cin >> n;
 
    vector<string>word(n);
    vector<char>letter;
 
    for (int i = 0; i < n; i++) {
        
        cin >> word[i];
        for (int j = 0; j < word[i].length();j++) {
            letter.push_back(word[i][j]);
        }
    }
 
    sort(letter.begin(), letter.end());
    letter.erase(unique(letter.begin(), letter.end()), letter.end());
 
    int m = letter.size();
    
    vector<int>d;
    for (int i = 9; i > 9 - m; i--) {
        d.push_back(i);
    }
 
    sort(d.begin(), d.end());
    int ans = 0;
 
    do {
        int now = calc(word, letter, d);
        if (ans < now) {
            ans = now;
        }
 
 
    } while (next_permutation(d.begin(), d.end()));
 
    cout << ans;
 
}