[C++] 백준 1339번 : 단어 수학

1339번: 단어 수학

---

문제

백준문제이미지

---

풀이

최대값을 구하는 문제이므로 큰 숫자들만 넣어서 조사해보면 된다.

 

각 알파벳에 숫자를 매칭시키기 위해 unique와 erase를 사용해서 중복된 알파벳을 제거시켜야 한다.

---

문제점

unique를 쓰기전에 반드시 sort가 필요하다.

또한 erase를 사용할 때 매개변수를 잘 확인해서 사용하는것을 주의하자.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

char alpha[256];

int calc(vector<string> &a, vector<char> &letters, vector<int> &d)
{
    int m = letters.size();
    int sum = 0;

    for (int i = 0; i < m; ++i)
    {
        alpha[letters[i]] = d[i];
    }

    for (string s : a)
    {
        int now = 0;
        for (char x : s)
        {
            now = now * 10 + alpha[x];
        }
        sum += now;
    }
    return sum;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int n;
    cin >> n;

    vector<string> a(n);
    vector<char> letters;

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        for (char x : a[i])
        {
            letters.push_back(x);
        }
    }

    sort(letters.begin(), letters.end());
    letters.erase(unique(letters.begin(), letters.end()), letters.end());
    // unique는 연속된 중복원소를 벡터의 맨 뒤로 보내버린다! -> 중복된 원소가 아닌 연속된 원소임을 주의!
    // sort했으므로 중복된 원소는 연속으로 쓰이게 된다!

    int m = letters.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(a, letters, d);
        if (ans < now)
        {
            ans = now;
        }
    } while (next_permutation(d.begin(), d.end()));
    cout << ans << "\n";

    return 0;
}

---

결과

결과 이미지

---

 

pyo7410/Study