[백준OJ] 1339번 단어 수학

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

1339번: 단어 수학

---

 

-풀이-

나온 알파벳들을 모두 저장해둔뒤, 백트래킹을 통해 알파벳에 부여할 수 있는 모든 경우의수를 구한뒤, 각 경우마다 치환된 숫자들의 합의 최댓값을 갱신시켜 주었다.

이때 부여를 할때 9부터 부여를 해주어야 제일 큰 경우가 나온다.

 

-시간복잡도-

나올 수 있는 최대 알파벳수가 10개이므로, 10! = 3,628,800 이 된다.

각 경우마다 모든 알파벳을 해당 숫자로 치환하며, 합을 구하는 로직은, 단어의 개수는 최대 10개이고, 각 단어의 길이는 최대 8이므로, 10*8이 된다. 이는 매우 작은수이므로, O(1) 이라고 봐도 된다.

따라서 각 알파벳에 숫자를 부여하는 시간복잡도만 고려해주면되므로 , 시간복잡도는 O(10!) 이 된다.

 

-코드-

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

bool visited[26] = { 0 };
int number[26] = { 0 };
int n;
vector<int> v;
vector<string> st;
int result = 0;

void dfs(int cnt, int num) {
	if (cnt == v.size()) {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int temp = 0;
			for (int j = 0; j < st[i].size(); j++) {
				char c = st[i][j];
				int ind = c - 'A';
				int d = number[ind];
				temp = temp * 10 + d;
			}
			sum += temp;
		}
		result = max(result, sum);
		return;
	}
	for (int i = 0; i < v.size(); i++) {
		if (number[v[i]]==-1) {
			number[v[i]] = num;
			dfs(cnt + 1, num - 1);
			number[v[i]] = -1;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		st.push_back(str);
	}
	for (int i = 0; i < 26; i++) {
		number[i] = -1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < st[i].size(); j++) {
			char c = st[i][j];
			int ind = c - 'A';
			if (!visited[ind]) {
				v.push_back(ind);
				visited[ind] = true;
			}
		}
	}
	dfs(0, 9);
	cout << result;

	return 0;
}