[BAE/<JOON> 문제풀이] 1036. 36진수

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

1036번: 36진수

서론

문제가 마음에 든다. 요즘 구현 문제들이 재밌는 것 같다. 

---

풀이

큰 수 연산 + 높은 진수 표현 문제다. 파이썬으로 풀면 편하지만 낭만이 없다.

1. 숫자가 36개 있으므로 각 숫자들이 각 자릿수에서 나타난 횟수를 저장한다.

2. 어떤 숫자가 Z ( 35 ) 로 바뀌면 35-숫자 만큼 추가되는 것이므로 Z로 바꿨을 때 얻을 수 있는 추가 합은

(36 - 숫자) * pow(10, 자리수) * 자리수에서 나타난 횟수 가 된다.

3. 이 값들을 구하고 정렬한 뒤, 원래 주어진 수에 k개 만큼만 더해서 답을 구할 수 있다.

 

틀렸던 점은 곱셈 연산을 구현할 때 Leading Zero가 생겼는데, 이 점을 몰라서 비교 함수가 제대로 동작하지 않았다.

두 수를 비교할 때 우선 자릿수부터 비교하도록 구현을 했기 때문에 Leading Zero가 생기면 대소관계 비교가 틀린다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
int dtot(char c) {
	if (c <= 9 + 48 && c >= 48) {
		return c - 48;
	}
	else if (c >= 'A' && c <= 'Z') {
		return c - 'A' + 10;
	}
	else return -1;
}
char ttod(int d) {
	if (d <= 9 && d >= 0) {
		return d + 48;
	}
	else if (d >= 10 && d <= 35) {
		return d + 55;
	}
	return -1;
}
struct t {
	vector<int> dig;
};
t convertt(string s) {
	t ret = { {} };
	for (int i = s.size() - 1; i >= 0; i--) {
		ret.dig.push_back(dtot(s[i]));
	}
	return ret;
}
t add(t a, t b) {
	if (a.dig.size() < b.dig.size()) {
		auto t = a; a = b; b = t;
	}
	t ret = { {} }; int c = 0;
	for (int i = 0; i < a.dig.size(); i++) {
		int s = a.dig[i];
		if (i < b.dig.size()) {
			s += b.dig[i];
		}
		s += c;
		c = s / 36;
		ret.dig.push_back(s % 36);
	}
	if (c != 0) {
		ret.dig.push_back(c);
	}
	return ret;
}
t power(t a, int c) {
	a.dig.insert(a.dig.begin(), c, 0);
	return a;
}
t mult(t a, t b) {
	if (a.dig.size() < b.dig.size()) {
		auto t = a; a = b; b = t;
	}
	t ret = { {} }; int c = 0;
	for (int j = 0; j < b.dig.size(); j++) {
		t cr = { {} };
		c = 0;
		for (int i = 0; i < a.dig.size(); i++) {
			int s = a.dig[i] * b.dig[j];			
			s += c;
			c = s / 36;
			cr.dig.push_back(s % 36);
		}
		if (c != 0) {
			cr.dig.push_back(c);
		}		
		cr = power(cr, j);
		ret = add(ret, cr);
	}	
	int pos = ret.dig.size() - 1;
	for (; pos >= 0; pos--) {
		if (ret.dig[pos] != 0) break;
	}	
	pos++;
	vector<int> rv(ret.dig.begin(), ret.dig.begin() + pos);
	return { rv };
}
bool cmp(t a, t b) {
	if (a.dig.size() == b.dig.size()) {
		for (int i = a.dig.size() - 1; i >= 0; i--) {
			if (a.dig[i] == b.dig[i]) continue;
			return a.dig[i] > b.dig[i];
		}
	}
	return a.dig.size() > b.dig.size();
}
int main()
{
	//ios::sync_with_stdio(0); cin.tie(0);		
	//freopen("input.txt", "r", stdin);
	auto ex = mult({ {1, 2, 3} }, { {0} });
	int n; cin >> n; vector<string> arr(n + 1);
	vector<vector<t>> dg(36, vector<t>(50)); // [숫자][숫자가나타난자릿수]=횟수
	t ts;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		for (int j = 0; j < arr[i].size(); j++) {
			int digit = dtot(arr[i][j]);
			int p = arr[i].size() - j - 1;
			dg[digit][p] = add(dg[digit][p], { {1} });
		}
		ts = add(ts, convertt(arr[i]));
	}		
	int k; cin >> k;	
	vector<t> sum = vector<t>(36);
	for (int i = 0; i < 36; i++) {
		for (int j = 0; j < 50; j++) {
			t total = mult(power({ {35 - i} }, j), dg[i][j]);
			sum[i] = add(sum[i], total);
		}
	}
	sort(sum.begin(), sum.end(), cmp);
	for (int i = 0; i < k; i++) {
		ts = add(ts, sum[i]);
	}
	for (int i = 0; i < ts.dig.size(); i++) {
		cout << ttod(ts.dig[ts.dig.size() - i - 1]);
	}
	return 0;
}