백준[1339] - 단어 수학

문제

백준 1339 문제 보기

접근 방법

여러 풀이 방법이 존재하지만 나는 모든 알파벳 조합을 만들고 수를 대입하는 방법으로 문제를 풀었다.

• 먼저, set을 활용해 중복없이 알파벳을 저장한다.
• set에 저장된 알파벳을 벡터에 저장한뒤 오름 차순으로 정렬한다.
• next_permutaion을 활용해 모든 조합을 만들어본다.

코드

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

int N, ans = 0;
vector<char> t;
vector<string> st;
set<char> s;
int arr[150];

// A == 65
int main() {
    cin >> N;
    for(int i = 0; i < N; i ++) {
        string temp;
        cin >> temp;
        // 문자열 저장
        st.push_back(temp);
        // 알파벳을 중복없이 저장
        for(int j = 0; j < temp.size(); j ++) {
            s.insert(temp[j]);
        }
    }
    // 알파벳을 벡터에 저장
    for(auto i = s.begin(); i != s.end(); i ++) {
        char c = *i;
        t.push_back(c);
    }
    // 오름차순 정렬
    sort(t.begin(), t.end());

    do {
        // 앞에서부터 하나씩 선택
        for(int i = 0, j = 9; i < t.size(); i ++, j --) {
            arr[t[i] - '0'] = j;
        }

        int sum = 0, tmp = 0;
        for(int i = 0; i < N; i ++, tmp = 0) {
            for(int j = 0; j < st[i].size(); j ++, tmp *= 10) {
                tmp += arr[st[i][j] - '0'];
            }

            sum += (tmp/10);
        }
        ans = max(ans, sum);
    } while(next_permutation(t.begin(), t.end()));

    cout << ans;
    return 0;
}