[C++/백준] 1339번-단어 수학

링크

---

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

문제

---

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

---

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

---

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

풀이

---

지금까지 풀었던 실버난이도 문제와는 다르게 골드부터는 문제를 풀 수 있는 핵심 아이디어가 중요하다는 것을 알려주는 문제였다.

단순하게 자리수가 높은 알파벳부터 큰 수를 할당하는 방법을 생각했지만 ABC+BDE와 같이 낮은 자리수의 같은 알파벳까지 고려해야한다.

더하기를 할때 알파벳들은 서로 떨어뜨려도 상관이 없다. 예를 들어 GCF+ACDEB는 G00+C0+F+A0000+C000+D00+E0+B와 같다고 할수있다.

따라서 각 알파벳이 나타낼 수 있는 최대 수를 배열에 저장하였고 sort를 이용하여 정렬시켰다.
가장 큰 수부터 9부터 0까지 곱해주어 결과값을 나타낸다.

코드

---

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

bool desc(int a, int b) {
	return a > b;
}

int main() {
	int N;

	int al[26];

	for (int i = 0; i < 26; i++) {
		al[i] = 0;
	}

	cin >> N;

	string tmp;
	int pow;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		pow = 1;
		for (int j = tmp.length() - 1; j >= 0; j--) {
			al[tmp[j] - 'A'] += pow;
			pow *= 10;
		}
	}
	sort(al, al + 26, desc);

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

	cout << result;

	return 0;
}