[백준] 1339번 단어 수학

1339번: 단어 수학

수학적으로 풀어도 되지만

백트래킹으로 풀어보았다.

 

계산에 사용되는 M개의 알파벳을 모아놓고

9부터 M개의 숫자를 순열로 대입하였다.

 

ex) ADC -> 3개의 숫자 9, 8, 7을 순열로 배치시키면

알파벳 ADC는

987, 978, 897, 879, 798, 789

이렇게 숫자가 대입될 수 있다.

 

map을 이용해서 각 알파벳에 숫자를 대입해주고

배치가 완료되면 단어의 합을 계산해주고 최댓값을 갱신한다.

 

이때 stoi를 이용하여 계산을 했었는데 시간 초과 나서

그냥 int형으로 계산해주니 통과되었다.

string형 계산이 시간 많이 걸리긴 하나보다.

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int N, Max;
string alphabet, word[11], num;
map <char, int> m;
bool chk[10] = { false };

void Permutation(int cnt) {
	if (cnt == alphabet.size()) {
		int res = 0;
		for (int i = 0; i < N; i++) {
			int tmp = 0;
			for (int j = 0; j < word[i].size(); j++) tmp = tmp*10 + m[word[i][j]];
			res += tmp;
		}
		Max = max(Max, res);
		return;
	}

	for (int i = 9; i >= 10 - (int)alphabet.size(); i--) {
		if (chk[i]) continue;
		chk[i] = true, m[alphabet[cnt]] = i;
		Permutation(cnt + 1);
		chk[i] = false;
	}
	
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word[i];
		for (int j = 0; j < word[i].size(); j++) {
			if (!m[word[i][j]]) {
				m[word[i][j]] = -1, alphabet += word[i][j];
			}
		}
	}

	Permutation(0);

	cout << Max;
	return 0;
}