백준 1339. 단어 수학

알고리즘 중급 문제 중 521 - 브루트 포스 - 순열(연습)

단어 수학

1. 간단 설명

---

N개의 단어가 주어진다

각 단어는 알파벳 대문자로 이루어져있고,

각 알파벳 대문자를 0~9 사이의 숫자 중 하나로 바꾸어, N개의 수를 합했을 때

주어진 단어의 합의 최대값을 출력하는 문제

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다

둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다

• 단어는 알파벳 대문자로만 이루어져있다

• 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다

• 서로 다른 문자는 서로 다른 숫자를 나타낸다

예시

---

예시 1)

AAA AAA

A = 9로 둘 경우

999 + 999로 1998이 최대값이 된다

예시 2)

GCF + ACBED 인 경우

A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7 로 놓았을 때

두 수의 합은 99437이 되어 최대가 된다

3. 알고리즘

---

각 자리수를 통해 풀이한다

예를들어 ABCD라면 A는 천의자리, B는 백의자리, C는 십의자리, D는 일의 자리이다

이를 이용해 A에 9를, B에 8을 할당하면

ABCD = 1000 * 9 + 100 * 8 + 10 * 7 + 1 * 6 = 9876 이 최대값이 된다

GCF + ACDEB는

G = 100
C = 10 + 1000
F = 1
A = 10000
D = 100
E = 10
B = 1

이므로

이를 정렬하면

A = 10000
C = 1010
G = 100
D = 100
E = 10
B = 1
F = 1 

이므로 A부터 차례대로 9부터 할당하면

(10000*9) + (1010*8) + 100*7 + 100*6 + 10*5 + 1*4 + 1*3 = 99437이 최대값이다

1. N과 문자열을 입력받는다
2. 해당 문자열을 입력 받으면서, 어느 자리수에 있는지 체크한 뒤 기록해둔다
3. 모든 문자를 입력 받았다면, 내림차순으로 정렬한다
4. 가장 큰 수 부터 9부터 할당하여, 모든 수에 숫자를 할당한다
5. 최대값을 출력한다

4. 소스코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int alphabet[26];

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;

	for (int i = 0; i < N; i++) {
		string input;
		cin >> input;

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

	sort(alphabet, alphabet + 26, greater<int>());

	int num = 9;
	int result = 0;

	for (int i = 0; i < 26; i++) {
		if (alphabet[i] == 0) break;
		result += alphabet[i] * num;
		num--;
	}

	cout << result;

	return 0;
}

완전 탐색으로 시도하려다가 탈탈 털렸다

재귀 함수를 이용해서 해당 알파벳에, 특정 수를 기록한 뒤

모든 문자에 숫자가 할당된 경우 이를 계산하려 했으나 시간초과로 틀렸다

각 문자가 사용되었는지 체크하고, 이 문자에 숫자를 할당하는 과정이

각 레벨별로 진행되어 연산이 너무 많아진게 원인인 것 같다