[백준][C++] 21275 폰 호석만

21275. 폰 호석만

21275번: 폰 호석만

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

폰 호석만보다 더 뛰어난 진법 변환 장인이 된 느낌이었다.

 

알고리즘 설계

1. 2진수부터 36진수까지의 A와 B를 10진수로 변환한 값을 배열에 넣는다.

변환 코드

long long Converter(int base, string number)
{
    long long result = 0;

    for (int i = number.size() - 1; i >= 0; i--)
    {
        int count = number.size() - i - 1;

        // alphabet
        if (isalpha(number[i]))
            result += (long long)((number[i] - 'a' + 10) * pow(base, count));

        // digit
        else
            result += (long long)((number[i] - '0') * pow(base, count));
    }

    return result;
}

2진수부터 36진수까지 계산해서 배열에 넣음

void Calculate(vector<long long>& arr, string str)
{
    // 최댓값 M
    char max = *max_element(str.begin(), str.end());

    // 2 ~ 36진법
    for (int i = 2; i <= 36; i++)
    {
        // M진수 이하일 때는 계산하지 않음
        if (isalpha(max) && i <= max - 'a' + 10)
            arr.push_back(-1);

        else if (isdigit(max) && i <= max - '0')
            arr.push_back(-1);

        else arr.push_back(Converter(i, str));
    }
}

A와 B의 각 숫자의 최댓값이 M이라고 하면, M + 1부터 36진수까지만 10진수로 변환한다.

 

2. A와 B 배열 중 서로 같은 수가 있는지 확인한다.

비교 코드

for (int i = 0; i < 35; i++)
{
    // 조건에 맞지 않으면 비교 X
    if (aArr[i] == -1 || aArr[i] >= pow(2, 63)) continue;

    auto bFind = find(bArr.begin(), bArr.end(), aArr[i]);

    // 같은 수를 발견하고 같은 진수가 아닐 때
    if (bFind != bArr.end() && i != bFind - bArr.begin())
    {
        results.push_back({ aArr[i], i + 2, bFind - bArr.begin() + 2 });
    }
}

X가 2^63 이상이거나 a를 N진수를 비교할 수 없을 때는 비교하지 않는다.

같은 수가 있다면 정답 배열에 저장한다.

 

3. 정답 배열의 길이가 0이면 "Impossible", 1이면 그 값을, 1 이상이면 "Multiple"을 출력한다.

if (results.empty())
    cout << "Impossible";

else if (results.size() > 1)
    cout << "Multiple";

else
    cout << results.front().x << " " << results.front().a << " " << results.front().b;

 

전체 코드

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

void Calculate(vector<long long>& arr, string str);
long long Converter(int base, string number);

struct Result
{
	long long x;
	int a, b;
};

int main()
{
	string a, b;
	cin >> a >> b;

	vector<long long> aArr;
	vector<long long> bArr;

	vector<Result> results;

	Calculate(aArr, a);
	Calculate(bArr, b);

	for (int i = 0; i < 35; i++)
	{
		// 조건에 맞지 않으면 비교 X
		if (aArr[i] == -1 || aArr[i] >= pow(2, 63)) continue;

		auto bFind = find(bArr.begin(), bArr.end(), aArr[i]);

		// 같은 수를 발견하고 같은 진수가 아닐 때
		if (bFind != bArr.end() && i != bFind - bArr.begin())
		{
			results.push_back({ aArr[i], i + 2, bFind - bArr.begin() + 2 });
		}
	}

	if (results.empty())
		cout << "Impossible";

	else if (results.size() > 1)
		cout << "Multiple";

	else
		cout << results.front().x << " " << results.front().a << " " << results.front().b;
}

void Calculate(vector<long long>& arr, string str)
{
	char max = *max_element(str.begin(), str.end());

	// 2 ~ 36진법
	for (int i = 2; i <= 36; i++)
	{
		// 최댓값 M
		// M진수 이하일 때는 계산하지 않음
		if (isalpha(max) && i <= max - 'a' + 10)
			arr.push_back(-1);

		else if (isdigit(max) && i <= max - '0')
			arr.push_back(-1);

		else arr.push_back(Converter(i, str));
	}
}

long long Converter(int base, string number)
{
	long long result = 0;

	for (int i = number.size() - 1; i >= 0; i--)
	{
		int count = number.size() - i - 1;

		// alphabet
		if (isalpha(number[i]))
			result += (long long)((number[i] - 'a' + 10) * pow(base, count));

		// digit
		else
			result += (long long)((number[i] - '0') * pow(base, count));
	}

	return result;
}

 

좀 복잡했지만, 진법 변환 마스터 폰 호석만만큼 진법 변환에 익숙해진 것 같다. 재밌는 문제!