단어 수학 (feat. 백준, 1339번)

단어 수학
https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
inline bool cmp(const pair<char, long long>& v1, const pair<char, long long>& v2) {
	return v1.second > v2.second;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	string str;
	map<char, long long> ans;
	cin >> N;
	for (register int n = 0, tmp; n < N; ++n) {
		cin >> str;
		tmp = 0;
		for (register int i = str.size() - 1; i >= 0; --i)
			ans[str.at(i)] += static_cast<long long>(pow(10, tmp++));
	}
	vector<pair<char, long long>> ansv(ans.begin(), ans.end());
	sort(ansv.begin(), ansv.end(), cmp);
	register long long answer = 0, temp = 9;
	for (auto& v : ansv)
		answer += v.second * (temp--);
	cout << answer;
	return 0;
}
// *&)*@*

 

1. 예로 ABC, BCA를 보겠습니다.
2. ABC = 100A + 10B + 1C, BCA = 100B + 10C + 1A 입니다.
   따라서 ABC + BCA = 101A + 110B + 11C 입니다.
3. 문자 앞의 값을 내림차순 기준으로 본다면 110B + 101A + 11C 순서이고 9부터 문자에 대입한다면
   110 * 9 + 101 * 8 + 11 * 7 = 1875 가 정답이 됩니다.