BOJ 1339 단어 수학

N개의 단어가 주어졌을 때 알파벳의 숫자(0~9)를 결정하고 단어를 숫자로 치환하여 수의 합을 최대로 만드는 문제이다. 처음에는 자릿수를 생각하지 않고 단순히 길이가 긴 단어의 첫번째 알파벳을 큰 값으로 설정하면 될것 같다고 생각하였다. 그래서 N개의 단어를 길이 기준으로 우선순위 큐에 넣고 하나씩 뽑으면서 subString을 구한 후 다시 큐에 넣어주는 방법으로 구현하였다. 예제는 모두 통과하였지만 1%에 틀렸다고 나왔다. 😂

 

그리고 질문 개시판을 확인해보다가 반례를 찾을 수 있었고 틀린 이유는 각 알파벳 마다 자릿수 가중치가 존재하고 이 가중치에 따라 결과가 달라질 수 있다는 것을 알게 되었다.

 

예를들어 

N=10

ABB

BC

BC

BC

BC

BC

BC

BC

BC

BC

 

다음과 같이 주어졌을 경우 길이를 기준으로 하면 A=9, B=9, C=7이렇게 설정할 수 있고 결과는 1771이 나온다.

하지만 자릿수 마다 가중치를 주었을때 A= 100, B=101, C=9 이렇게 결과가 나오고 따라서 B - A - C 순서대로 숫자를 부여해야 한다. 가중치를 반영하여 계산을 해보면 결과는 1772가 나온다.

 

당연한 결과이다. A=9, B=8 로 설정하면 각각 900,808 이 나오고  A=8, B=9로 설정하면 각각 800,909 가 나온다.

 

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

int alpa[26];
vector<pair<int, int>> weight;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	return a.first > b.first;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	memset(alpa, -1, sizeof(alpa));
	for(int i = 0; i < 26; i++)
	{
		weight.push_back({ 0,-1 });
	}

	int n;

	cin >> n;

	vector<string> v;

	for(int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		v.push_back(s);
		for(int j = 0; j < s.size(); j++)
		{
			weight[s[j] - 'A'].first += pow(10, s.size() - j);
			weight[s[j] - 'A'].second = s[j] - 'A';
		}
	}

	sort(weight.begin(), weight.end(),cmp);

	int num = 9;
	for(int i = 0; i < 10; i++)
	{
		alpa[weight[i].second] = num;
		num--;
	}
	
	int maxNum = 0;
	for(int i = 0; i < v.size(); i++)
	{
		string result = "";
		for(int j = 0; j < v[i].size(); j++)
		{
			result.append(to_string(alpa[v[i][j] - 'A']));
		}
		maxNum += stoi(result);
	}

	cout << maxNum;
}