[백준 1339] 단어 수학 (C++)

문제 링크: https://www.acmicpc.net/problem/1339

1339번: 단어 수학

1. 주의할 점

- 알파벳이 최대 10개 -> A~Z 사이 임의의 10개가 최대다

 

2. 구현

- 첫 번째 방법: 브루트포스(DFS)를 이용하여 구현한다

- 알파벳을 모든 경우로 배치하는 방법 : 10! -> 약 360만이므로 2초내에 충분히 계산 가능하다

 

- 두 번째 방법: 그리디 알고리즘으로 푼다

- 각 알파벳이 해당 자리수에 어떤 수를 대입받기 전에 얼마만큼의 수를 나타낼 수 있는지 계산한다

Ex) ABC CA

A: 100 + 1 = 101

B: 10

C: 1 + 10 = 11

- 각 알파벳이 나타낼 수 있는 수가 가장 큰 수부터 9,8,7,....,2,1 순서로 할당해준다

 

[브루트포스] - 492ms

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> word;
int result = -1;
vector<char> alpha;				//들어있는 알파벳
bool type[26] = { false, };		//어떤 알파벳이 사용되었는지 확인
bool check[10];
vector<int> v;			//각 알파벳에 해당하는 숫자

void cal() {
	int t_result = 0;
	int cnt = 0;
	int a[26];
	for (int i = 0; i < alpha.size(); i++) {
		char c = alpha[i];
		int num = v[i];
		a[c - 'A'] = num;
	}
	for (int i = 0; i < word.size(); i++) {
		int temp = 0;
		for (int j = 0; j < word[i].size(); j++) {
			temp *= 10;
			temp += a[word[i][j] - 'A'];
		}
		t_result += temp;
	}
	result = max(result, t_result);
}

void dfs(int cnt) {
	if (cnt == 10) {
		cal();
		return;
	}
	for (int i = 10 - alpha.size(); i < 10; i++) {
		if (!check[i]) {
			v.push_back(i);
			check[i] = true;
			dfs(cnt + 1);
			check[i] = false;
			v.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num;
	string ss;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> ss;
		word.push_back(ss);
		for (int j = 0; j < ss.size(); j++) {
			int c = ss[j] - 'A';
			if (!type[c]) {
				type[c] = true;
				alpha.push_back(ss[j]);
			}
		}
	}
	dfs(10 - alpha.size());
	cout << result;
	system("pause");
	return 0;
}

 

 

[그리디] - 0ms

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> word;
int result = 0;
int alpha[26];		//어떤 알파벳이 사용되었는지 확인

void cal() {
	for (int i = 0; i < word.size(); i++) {
		int pow = 1;
		for (int j = word[i].size() - 1; j >= 0; j--) {
			int val = word[i][j] - 'A';
			alpha[val] += pow;
			pow *= 10;
		}
	}
	sort(alpha, alpha + 26);
	int num = 9;
	for (int i = 25; i >= 0; i--) {
		if (alpha[i] == 0) break;
		result += (alpha[i] * num);
		num--;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num;
	string ss;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> ss;
		word.push_back(ss);
	}
	cal();
	cout << result;
	system("pause");
	return 0;
}