[백준]1339_단어 수학

https://www.acmicpc.net/problem/1339

Solved

✔ (way1) 0~9를 최대 10개의 알파벳에 매핑해햐 하니 전체 경우의 수는 10!=362만 정도. 브루트 포스가 가능하다. 순열해도 좋고, dfs로 조합을 구해도 좋을듯
✔ (way2)브루트 포스 외에도 수학적인 방법으로도 풀 수 있다.
예를 들어 abc+bca를 구할 때 이를 101*a+110*b+11*c로 표현할 수 있으니 곱하는 수가 가장 큰 알파벳부터 큰 값을 주면 답이 나온다.

//way1
using namespace std;
#include <iostream>
#include <vector>
vector<int> numberArr; //dfs로 넣은 수들 
vector<chart> existAlphabet //들어있는 알파벳만
int numOfAlphabet = 0;
int answer = -1;

void dfs(int idx) {
	if(idx===numOfAlphabet) {
    	answer = max(answer, calRes());
        return;
    }
    for(int i=10-existAlphabet.size(); i<10; i++) {
    	if(visitedNum[i]) continue;
        visitedNum.push(i);
        visitedNum[i] = true;
        dfs(idx+1);
        visitedNum[i] = false;
        visitedNum.pop();
    }
}

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

int alpha[26];
bool compare(int a, int b) {
	return a > b;
}
int main() {
	vector<string> input;
	int n, answer = 0;
	string s;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		input.push_back(s);
	}

	for (int i = 0; i < n; i++) {
		int pow = 1;
		for (int j = input[i].size()-1; j >= 0; j--) {
			alpha[input[i][j] - 'A'] += pow;
			pow *= 10;
		}
	}

	sort(alpha, alpha + 26, compare);

	int k = 9;
	for (int i = 0; i <26; i++) {
		if (alpha[i] == 0) break;
		answer += alpha[i] * (k - i);
	}
	cout << answer << '\n';
}