[백준] 1339번 단어 수학

문제 링크: https://www.acmicpc.net/problem/1339

문제

문제 이해

입력으로 문자열들이 들어오고, 문자열들은 행으로 나눠진다. 그리고 알파벳들이 숫자로 대체되고, 동일한 알파벳은 동일한 숫자를 가진다. 숫자로 대체된 문자열들의 합을 구하고, 합이 가장 클 때의 값을 구하면 되는 문제이다.

문제 접근

나는 이 문제를 brute force로 접근하였다. 전전 문제인 부등호와 동일하게 dfs를 사용하였다. 부등호 문제와 매우 유사하여서, 금방 풀 수 있었다.
나는 먼저 들어온 문자열의 알파벳 숫자를 찾았고, 그리고 dfs를 진행하였다. dfs에서는 알파벳 만큼 숫자가 채워지면 문자열을 계산하도록 하였다. 그리고 문자열들을 숫자로 나타냈을 때 최댓값만 구하면 되기 때문에, 10개의 숫자에서 뒤에서부터 알파벳 갯수만큼의 수들만 고려해서 계산하면된다.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> result;
vector<int> check_num; // 가지고 있는 숫자들
bool check[10];
vector<char> alpha;// 입력받은 알파벳
vector<string> values;//입력받은 문자열들
int num;
int num_alpha;// 입력받은 알파벳의 갯수
int alpha_get_num[26]; // 알파벳과 숫자를 대응시킬 array

void cal_str(){
    for(int i = 0 ; i < num_alpha ; i++){
        int a = alpha[i] - 'A';
        int n = check_num[i];
        alpha_get_num[a] = n;
    }
    int cur_result = 0;
    for(int i = 0 ; i < values.size() ; i++){
        int temp_result = 0 ;
        for(int j = 0 ; j < values[i].length() ; j++){
            temp_result *= 10;
            temp_result += alpha_get_num[values[i][j] - 'A'];
        }
        cur_result += temp_result;
    }
    result.push_back(cur_result);
}
void dfs(int count){
    if(count == num_alpha){
        cal_str();
    }
    else{
        for(int i = 10 - num_alpha; i <= 9 ; i++){
            if(!check[i]){
                check_num.push_back(i);
                check[i] = true;
                dfs(count+1);
                check[check_num.back()] = false;
                check_num.pop_back();
            }
        }
    }
    return;
}
int check_len(){
    bool alpha_ch[26] = {false,};
    int number = 0;
    for(int i = 0 ; i < num ; i++){
        string temp = values[i];
        for(int j = 0 ; j < values[i].length() ; j++){
            if(alpha_ch[values[i][j] - 'A'] == false ){
                alpha_ch[values[i][j] - 'A'] = true;
                alpha.push_back(values[i][j]);
                number++;
            }
        }
    }
    return number;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> num;
    string temp;
    for(int i = 0 ; i < num ; i++){
        cin >> temp;
        values.push_back(temp);
    }
    num_alpha = check_len();
    dfs(0);
    sort(result.begin(),result.end());
    cout << result.back() << "\n";
}

평가

전에 dfs를 활용한 brute force문제를 풀어보지 않았다면, 푸는데 오랜 시간이 걸렸을 거 같은 문제이다. 그리고 접근 방법을 찾아보니 greedy로 푸는 방법도 존재했다. greedy와 dp를 공부하여, 포스트를 올려야 겠다.