[백준][C++] 1036: 36진수

문제 링크: https://www.acmicpc.net/problem/1036

문제번호가 1000+36 이라서 36진수 문제인 것 같습니다.

진법변환에 익숙하지 않은 사람한테는 좋은 연습문제가 될 수도 있겠습니다...

 

좀 여러가지를 생각해봐야 하는데, 일단 단어의 길이가 최대 50이기 때문에 C++의 정수형으로 표현하기 곤란합니다. 파이썬이나 자바는 BigInteger가 있으니 그거 쓰면 될 것 같고요, C++은 직접 구현해줘야 합니다.

 

그리고 각 자릿수별로 diff=digit의 출현빈도*(Z와 digit의 차이)를 계산해 diff 상위 k개 digit를 뽑는 방법을 생각해볼 수 있겠는데요, 반례가 있습니다.

//입력
50
XWW
WW
WW
..
WW
1

//출력 (W->Z로 바꿨을 때)
2AYM

자릿수별로 뽑으면 위 입력에서는 제일 높은 자릿수에 있는 X를 그냥 뽑아버리겠죠.

즉, 자릿수별로 차이를 계산하면 안되고, 모든 자릿수의 차이를 누적해 계산해야 합니다.

 

알고리즘은 대략 아래와 같습니다.

• 1. int histogram[51][36]
  [자릿수][digit]의 개수를 저장하는 배열을 만들고 0으로 초기화
• 2. 단어 한개씩 입력받을 때마다 히스토그램에 누적
  • 이때 histogram이 36개가 되는 자리수가 생기면 덧셈할 때처럼 0으로 만들고 carry를 올린다
• 3. 이제 히스토그램을 이용해 각 digit를 Z로 바꿨을 때 값이 얼마나 늘어나는지 계산한다
  
  • 이 값은 long long 범위를 훌쩍 넘어가니 정수형은 사용 불가
• 4. 값이 가장 많이 늘어나는 digit k개를 골라 단어들의 해당 digit를 Z로 바꾼다
• 5. 단어들을 전부 더한 값을 출력한다

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;



int histogram[51][36];	//[자릿수][해당digit] 개수 (0~35)


//36(digit) -> dec
constexpr int trans_digit(char n) {
	if (n>='0' && n<='9')
		return n-'0';
	return n - 'A' + 10;
}

//dec(digit) -> 36
constexpr char rtrans_digit(int n) {
	if (n < 10)
		return static_cast<char>(n+'0');
	return static_cast<char>(n-10+'A');
}

//dec(num) -> 36
string rtrans(int n) {
	string ret;

	while (n) {
		ret += rtrans_digit(n % 36);
		n /= 36;
	}

	reverse(ret.begin(), ret.end());
	return ret;
}

//36(num) + 36(num)
string add(string a, string b) {
	// a>=b가 되도록 (자릿수)
	if (b.size() > a.size())
		swap(a, b);

	// b 앞에 0으로 채움
	b = string(a.size()-b.size(), '0') + b;

	string ret;

	int carry=0;
	for (auto it1=a.rbegin(), it2=b.rbegin();
		it1 != a.rend();
		++it1, ++it2)
	{
		int sum = carry + trans_digit(*it1) + trans_digit(*it2);
		carry = sum / 36;
		sum %= 36;

		ret += rtrans_digit(sum);
	}

	if (carry)
		ret += '1';

	reverse(ret.begin(), ret.end());
	return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, k;
	cin >> n;

	vector<string> words(n);
	for (auto& w : words) {
		cin >> w;

		int counter = 0;	//자릿수
		for (auto rit = w.rbegin();
			rit != w.rend();
			++rit, ++counter) {
			int digit = trans_digit(*rit);
			++histogram[counter][digit];

			// carry 발생
			if (histogram[counter][digit] == 36) {
				int current_idx = counter;
				while (histogram[current_idx][digit] == 36) {
					histogram[current_idx][digit] = 0;
					++current_idx;
					++histogram[current_idx][digit];
				}
			}
		}
	}

	cin >> k;
	vector<char> candidates;	// Z로 바꿀거

	vector<pair<string, int>> vp;	// diff, digit_idx
	for (int i = 0; i < 35; ++i) {	//z 빼고
		string diff;
		for (int j = 0; j < 51; ++j) {
			if (histogram[j][i]) {
				string s = rtrans(histogram[j][i] * (35-i)) + string(j, '0');
				diff = add(diff, s);
			}
		}

		vp.emplace_back(diff, i);
	}

	sort(vp.begin(), vp.end(), [](auto& lhs, auto& rhs) {
		auto &[s1, ign1] = lhs;
		auto &[s2, ign2] = rhs;
		
		if (s1.size() != s2.size())
			return s1.size() > s2.size();

		return s1 > s2;
	});

	for (int i = 0; i < min(k,35); ++i)
		candidates.push_back(rtrans_digit(vp[i].second));


	// 알파벳 변환
	for (auto& w : words) {
		for (auto& c : candidates) {
			replace(w.begin(), w.end(), c, 'Z');
		}
	}

	// 더함 (36진수)
	string ans;
	for (auto& w : words)
		ans = add(ans, w);
	cout << ans << '\n';

	return 0;
}

코드가 좀 기네요. 짜는데 힘을 다 쏟아버렸습니다..