[BAE/<JOON> 문제풀이] 1132. 합

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

1132번: 합

핵심::
그리디긴 한데 구현에 더 가까운 문제같다.

풀이::
우선 알파벳들이 각각의 자리에서 몇번씩 나오는지 계산하고 그 값을 숫자로 치환한다.

10의 자리에서 한번 출현, 1의 자리에서 12번 출현 -> 22 로 치환

해당 값들을 크기 순으로 내림차순 정렬하고 높은 값부터 큰 숫자를 주고 값을 계산하면 된다.

의견::
그리디같은 구석이 없어서 풀 만한 문제

코드::

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

struct tv {
	int p = -1;
	int cnt[13] = { 0, };
	long long sum = 0;
};

vector<tv> cnt(10);

bool cmp2(tv a, tv b) {
	return a.sum < b.sum;
}

int main()
{
	int n; cin >> n;
	vector<string> arr(n + 1);
	int m = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		m = (m > arr[i].size() ? m : arr[i].size());
	}

	sort(arr.begin(), arr.end());
	for (int i = 1; i <= arr.size() / 2; i++) {
		auto v = arr[i];
		arr[i] = arr[arr.size() - i];
		arr[arr.size() - i] = v;
	}

	vector<vector<short>> t(n + 1, vector<short>(m + 1));

	vector<bool> zable(10, true);

	for (int i = 1; i <= n; i++) {
		int sz = arr[i].size();
		zable[arr[i][0] - 65] = false;
		for (int j = 1; j <= m - sz; j++) {
			t[i][j] = -1;
		}

		for (int j = m - sz + 1; j <= m; j++) {
			t[i][j] = arr[i][j - (m - sz + 1)] - 65;
		}
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (t[j][i] == -1) continue;
			cnt[t[j][i]].p = t[j][i];
			cnt[t[j][i]].cnt[i]++;
		}
	}

	for (int i = 0; i < 10; i++) {
		for (int j = 1; j <= m; j++) {
			cnt[i].sum += pow((long long)10, (long long)j - 1) * (long long)cnt[i].cnt[m - j + 1];
		}
	}

	sort(cnt.begin(), cnt.end(), cmp2);

	vector<int> tq(10, -1);	

	int ck = 0;
	if (cnt[0].p != -1) {
		for (int i = 0; i < 10; i++) {
			if (cnt[i].p == -1) continue;
			if (zable[cnt[i].p] == true) {
				tq[cnt[i].p] = 0;
				ck = 1;
				break;
			}
		}
	}

	for (int i = 0; i < 10; i++) {
		if (cnt[i].p == -1) continue; 
		if (tq[cnt[i].p] == 0) {
			ck = 0;
			continue;
		}
		tq[cnt[i].p] = i + ck;
	}


	/*int dpint = -1;
	int mp;
	for (int i = 1; i <= n; i++) {
		int num = arr[i][0] - 65;
		long long mn = 9223372036854775807;
		if (zable[num] == false && tq[num] == 0) {
			for (int j = 0; j < 10; j++) {
				if (zable[cnt[j].p] == false) continue;
				if (mn > cnt[cnt[j].p].sum) {
					mn = cnt[j].sum;
					mp = cnt[j].p;
				}
			}			
			dpint = tq[mp];
			tq[mp] = 0;
		}
	}

	for (int i = 0; i < 10; i++) {
		if (tq[i] < dpint && i != mp) tq[i]++;
	}*/

	long long sum = 0;

	for (int i = 1; i <= n; i++) {
		int sz = arr[i].size();
		for (int j = sz - 1; j >= 0; j--) {
			sum += (long long)tq[arr[i][j] - 65] * pow((long long)10, (long long)sz - j - 1);
		}
	}

	cout << sum;

	return 0;
}