백준 21275 폰 호석만

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

21275번: 폰 호석만

#include <iostream>
#include <cmath>

using namespace std;

long long cal(int n, string s) {

    long long res = 0;
    int ptmp = 0;

    for (int i = s.size() - 1; i >= 0; i--) {
        int cur;
        if (isalpha(s[i])) {
            cur = s[i] - 'a' + 10;
        } else {
            cur = s[i] - '0';
        }

        res += pow(n, ptmp) * cur;
        ptmp++;
    }

    return res;
}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string a, b;
    int xans, aans, bans;

    cin >> a >> b;

    int amax = 0, bmax = 0;
    for (int i = 0; i < a.size(); i++) {
        if (isalpha(a[i])) {
            amax = max(amax, a[i] - 'a' + 11);
        } else {
            amax = max(amax, a[i] - '0' + 1);
        }
    }

    for (int i = 0; i < b.size(); i++) {
        if (isalpha(b[i])) {
            bmax = max(bmax, b[i] - 'a' + 11);
        } else {
            bmax = max(bmax, b[i] - '0' + 1);
        }
    }

    int cnt = 0;

    for (int i = amax; i <= 36; i++) {
        for (int j = bmax; j <= 36; j++) {
            long long atmp = cal(i, a);
            long long btmp = cal(j, b);

            if (i == j) {
                continue;
            }

            if (atmp == btmp && atmp >= 0) {
                cnt++;
                if (cnt >= 2) {
                    cout << "Multiple";
                    return 0;
                }
                xans = atmp;
                aans = i;
                bans = j;
            }
        }
    }


    if (cnt == 0) {
        cout << "Impossible";
    } else {
        cout << xans << " " << aans << " " << bans;
    }




    return 0;
}

 

 솔직히 보고 브루트포스 문제라는 생각이 안 들었다. 하나씩 차근차근히 뜯어보자.

 

1. amax, bmax 구하기

 

    int amax = 0, bmax = 0;
    for (int i = 0; i < a.size(); i++) {
        if (isalpha(a[i])) {
            amax = max(amax, a[i] - 'a' + 11);
        } else {
            amax = max(amax, a[i] - '0' + 1);
        }
    }

    for (int i = 0; i < b.size(); i++) {
        if (isalpha(b[i])) {
            bmax = max(bmax, b[i] - 'a' + 11);
        } else {
            bmax = max(bmax, b[i] - '0' + 1);
        }
    }

 

우선 해당 입력값으로 표현할 수 있는 최소 진수를 구한다. "ep"를 예로 들자면 p를 해당 진수에서 나타낼 수 있는 최댓값이라 보면 p는 25이므로 26진수부터 나타낼 수 있다. 이 이하는 자릿수 올림이 발생하기 때문이다.

 

2. 값 구하기

for (int i = amax; i <= 36; i++) {
        for (int j = bmax; j <= 36; j++) {
            long long atmp = cal(i, a);
            long long btmp = cal(j, b);

            if (i == j) {
                continue;
            }

            if (atmp == btmp && atmp >= 0) {
                cnt++;
                if (cnt >= 2) {
                    cout << "Multiple";
                    return 0;
                }
                xans = atmp;
                aans = i;
                bans = j;
            }
        }
    }

 위에서 구한 진수부터 문제에서 제한한 진수까지 모든 경우를 10진수로 치환한다. 그 후 두 값이 같다면 이 값을 저장한다. 나타낼 수 있는 값이 두 개 이상일 경우 더 이상 연산이 불필요하므로 Multiple을 출력하고 프로그램을 종료한다.

 

 이후 cnt에 따라 값을 출력하면 된다.