백준 1339 - 단어 수학

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, A~Z를 0~9로 적절히 치환하여 주어진 단어들의 합을 최대로 만드는 것이다.

 

가장 먼저 드는 생각은 자릿수가 큰 문자부터 9로 바꾸면 될 것 같다.

만약, 자릿수가 같은 문자가 있다면 더 많이 나온 문자를 9로 바꾸면 될 것이다.

 

이러한 규칙은 아주 틀린 것은 아니지만 예외가 존재할 수 있다.

모든 단어는 최대 10개가 주어진다.

이 것이 의미하는 것은 한 자리에 똑같은 문자가 10개까지 나올 수 있다는 뜻이다.

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

위의 예시를 앞서 말한 규칙대로 적용한다면 A는 최대 세 번째 자릿수이기 때문에 9, B는 최대 두 번째 자릿수이기 때문에 8로 치환할 것이다.

하지만 B를 9로 A를 8로 치환해야 최댓값이 된다.

위의 규칙이 깨진 이유는 B가 두 번째 자릿수에 10번, 첫 번째 자릿수에 10번 나왔기 때문이다.

한 자리에 10번 나왔다는 것은 그 앞 자릿수와 동일하다는 뜻이다.

10은 1이 10번 있는 것과 같은 논리이다.

따라서, 같은 자리에 10번 나온 수는 앞 자리 수로 세어줘야 한다.

하지만 이를 모두 살펴보며 자리를 바꿔주는 것은 복잡한 과정이다.

이를 간단하게 수로 표현한다면 문자들의 순서를 쉽게 구할 수 있다.

1의 자리, 10의 자리, 100의 자리 등으로 표현하여 문자에 값을 더하면 된다.

for (int i = 0; i < N; i++)
{
    int len = words[i].length();
    for (int j = 0; j < len; j++)
    {
        int letterIdx = words[i][j] - 'A';
        alpha[letterIdx].first += pow(10, len - j);
        alpha[letterIdx].second = words[i][j];
    }
}

 

이 과정이 끝나면 정렬하여 9부터 치환하면 된다.

sort(alpha.begin(), alpha.end(), greater<pair<int, char>>());

int v = 9;
for (auto& [order, letter] : alpha)
{
    if (v < 0 || letter < 'A') break;
    value[letter - 'A'] = v--;
}

int ans = 0;
for (int i = 0; i < N; i++)
{
    ans += MakeNum(words[i]);
}

cout << ans;

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<string> words;
vector<pair<int,char>> alpha(26);
vector<int> value(26);

int MakeNum(string word)
{
	int result = 0;
	for (int i = 0; i < word.length(); i++)
	{
		result *= 10;
		result += value[word[i] - 'A'];
	}

	return result;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		words.push_back(str);
	}

	for (int i = 0; i < N; i++)
	{
		int len = words[i].length();
		for (int j = 0; j < len; j++)
		{
			int letterIdx = words[i][j] - 'A';
			alpha[letterIdx].first += pow(10, len - j);
			alpha[letterIdx].second = words[i][j];
		}
	}

	sort(alpha.begin(), alpha.end(), greater<pair<int, char>>());

	int v = 9;
	for (auto& [order, letter] : alpha)
	{
		if (v < 0 || letter < 'A') break;
		value[letter - 'A'] = v--;
	}

	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		ans += MakeNum(words[i]);
	}

	cout << ans;

	return 0;
}

---