[C++] BOJ / 1339번 / 단어 수학

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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

2
GCF
ACDEB

출력

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

99437

풀이

입력받은 단어의 자릿수마다 10의 거듭제곱을 구하는 방식으로 풀이하였습니다.

 

효율적인 풀이 방법을 찾는 과정은 시간이 꽤 걸렸지만 구현하는 것은 그리 어렵지 않았습니다.

---

#include<iostream>
#include<algorithm>
#include<math.h>

using namespace std;

int n, ans = 0;
int alp[26];

bool compare(int a, int b)
{
	if (a > b) return true;

	return false;
}

void input()
{
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		string word;
		cin >> word;

		for (int j = 0; j < word.length(); ++j)
			// 자릿수에 따라 10의 거듭제곱 적용
			alp[word[j] - 'A'] += pow(10, word.length() - j - 1);
	}

	sort(alp, alp + 26, compare);	// 내림차순 정렬
}

void solve()
{
	int num = 9;

	for (int i = 0; i < 26; ++i)
	{
		if (alp[i] != 0)
		{
			ans += alp[i] * num;
			--num;
		}
	}

	cout << ans << '\n';
}

void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main()
{
	init();
	input();
	solve();

	return 0;
}